Lidt om algoritmen:
Merge sort fungerer på følgende måde:
Hvis man skal sortere en stak kort alfabetisk, deles stakken i to. Hver stak sorteres uafhængigt.
Da hver stak skal sorteres uafhængigt gælder det også her at hver stak deles i to rekursivt indtil størrelsen på stakkene er på en.
Herefter samles understakkene igen indtil hele listen er samlet igen, hvor listen så skulle være sorteret.

Derfor indeholder merge sort to stadier:
Det første stadie deler listen op i under lister på et element hver, samt samlingen af den til det sorterede array.
Det andet stadie samler hver af under listerne, startende nederst og arbejder sig derefter op.

Hvis merge sort implementeres på et array, skal der erkløres et midlertidigt array, da det oprindelige array deles op i to førend det sorteres.
Dette er nødvendigt da alle elementerne kan have skiftet position inden sorteringen er færdig, betyder at der skal erklæres et midlertidigt array af samme størrelse som det oprindelige til at arbejde i.

Hastighed:
Merge sort foretager ca. dobbelt så mange assigments som sammenligninger, hvilket ikke er godt, da assignments tager længere tid end sammenligninger.
Det ligger dog betydeligt under det antal insertion sort bruger.

Når merge sort implementeres med arrays ligger den mellem at være en O(n log n) algoritme og en O(2n log n) algoritme.
Hvis den derimod var implementeret på en linked liste ville den komme meget tæt på at være en O(n log n) algoritme, hvilket gør den til en af de mest effektive sorteringsalgoritmer.

Eksempel:
Sourcekode til eksempel:
SortAlgorithm.java
MyMergeSort.java

Eksemplet er implementeret på et array.
MyMergeSort.java indeholder metoden sort( int[] a, int lo, int hi ) der udfører sorteringen.
Det første der sker her er at metoden kalder sig selv rekursivt indtil arrayet er delt op i størrelser på et element.
Herefter starter while løkken, der sorterer og samler stumperne.