Merge sort är en dela-och-härska, stabil sortering som körs i garanterad O(n log n) tid. Den delar upp arrayen på mitten, sorterar varje halva rekursivt och slår sedan ihop de två sorterade halvorna.
Idén
Ett enda element är redan sorterat (basfall). Sammanslagning av två sorterade listor är linjär, och vi gör log n nivåer av sammanslagning.
