Merge Sort
Teilt rekursiv in zwei Hälften, sortiert beide und verschmilzt sie wieder in einem Puffer.
- Vergleiche 0
- Tauschvorgänge 0
- sortierte Indizes 0
- aktiver Bereich
- Vergleich
- Tausch
- sortiert
Merge-Puffer
Pseudocode
1 mergeSort(lo, hi)
2 if lo >= hi: return
3 mid = (lo + hi) / 2
4 mergeSort(lo, mid)
5 mergeSort(mid + 1, hi)
6 merge(lo, mid, hi)
7 merge(lo, mid, hi)
8 copy a[lo..mid] to L, a[mid+1..hi] to R
9 while i < |L| and j < |R|
10 if L[i] <= R[j]: a[k++] = L[i++]
11 else: a[k++] = R[j++]
12 copy remaining L into a
13 copy remaining R into a
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Merge Sort folgt dem Divide-and-Conquer-Prinzip. Die Divide-Phase halbiert das Array rekursiv so lange, bis nur noch Bereiche der Länge 1 übrig sind (per Definition sortiert). Die Conquer-Phase verschmilzt anschließend Paare benachbarter sortierter Bereiche zu einem größeren sortierten Bereich, indem zwei Zeiger durch die jeweils sortierten Hälften L und R laufen und das jeweils kleinere Element in einen Hilfspuffer geschrieben wird. Sobald eine Seite leer ist, wird der Rest der anderen einfach hinten angehängt. Der Puffer wird am Ende zurück in das Ursprungs-Array kopiert. Weil die Rekursion das Array log2(n) mal halbiert und jeder Merge-Schritt insgesamt O(n) Arbeit kostet, liegt die Gesamtlaufzeit immer bei O(n log n), egal welche Eingabe vorliegt: Best, Average und Worst Case sind identisch. Der Algorithmus benötigt einen linearen Hilfspuffer (O(n) Zusatz-Speicher). Die Reihenfolge gleichwertiger Elemente bleibt erhalten, Merge Sort ist stabil.
Komplexität
- Best Case
O(n log n) - Average Case
O(n log n) - Worst Case
O(n log n) - Zusatz-Speicher
O(n)
Wann verwenden?
Erste Wahl, wenn Stabilität gefordert ist, also gleichwertige Elemente ihre relative Reihenfolge behalten sollen, oder wenn die Daten von einer Festplatte oder einem Netz-Stream kommen. Merge Sort verarbeitet die Eingabe sequentiell und lässt sich als External Sort auf Datenmengen ausdehnen, die nicht in den Hauptspeicher passen.