Merge sort er en divide-and-conquer, stabil sortering som kjører i garantert O(n log n) tid. Den deler arrayen i to, sorterer hver halvdel rekursivt, og slår så sammen de to sorterte halvdelene.
Ideen
Et enkelt element er allerede sortert (base case). Sammenslåing av to sorterte lister er lineær, og vi gjør log n nivåer av sammenslåing.
