Merge sort er en divide-and-conquer, stabil sortering, der kører i garanteret O(n log n) tid. Den deler arrayet i halvdele, sorterer hver halvdel rekursivt og fusionerer derefter de to sorterede halvdele.
Ideen
Et enkelt element er allerede sorteret (basistilfælde). Fusionering af to sorterede lister er lineær, og vi udfører log n niveauer af fusionering.
