Merge Sort
VergleichsbasiertTeilt das Array rekursiv in Hälften, bis einzelne Elemente übrig sind, und fügt sortierte Hälften wieder zusammen — garantiert O(n log n).
Live-Visualisierung
Komplexität
| Bester Fall | O(n log n) |
| Durchschnitt | O(n log n) |
| Schlechtester Fall | O(n log n) |
| Speicherkomplexität | O(n) |
| Stabiles Sortieren | Ja |
| In-Place | Nein |
Legende
O(1)- Konstant: Egal wie viele Elemente — der Aufwand bleibt gleich.
O(n)- Linear: Doppelt so viele Elemente → doppelt so viel Aufwand.
O(n log n)- Quasi-Linear: Wenig schlechter als linear — der Goldstandard für Sortieren.
O(n²)- Quadratisch: 10× mehr Elemente → 100× mehr Aufwand. Langsam bei großen Listen.
Stabil- Stabile Sortierung: Gleiche Werte behalten ihre ursprüngliche Reihenfolge zueinander.
In-Place- In-Place: Sortiert direkt im vorhandenen Speicher, ohne eine Kopie der Liste anzulegen.
Vergleichsbasiert- Vergleichsbasiert: Der Algorithmus entscheidet nur durch „ist A kleiner als B?" — funktioniert mit beliebigen Werten.
Nicht-Vergleichsbasiert- Nicht-Vergleichsbasiert: Nutzt die Struktur der Zahlen selbst (z. B. Ziffern) — kann dadurch schneller als O(n log n) sein.
Implementierung
TypeScript-Implementierung — direkt kopierbereit.
function mergeSort(arr: number[]): number[] {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left: number[], right: number[]): number[] {
const result: number[] = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) result.push(left[i++]);
else result.push(right[j++]);
}
return [...result, ...left.slice(i), ...right.slice(j)];
}Wie es funktioniert
Merge Sort ist ein klassischer Teile-und-Herrsche-Algorithmus. Er teilt das Array rekursiv in Hälften, bis jedes Teilarray nur noch ein Element enthält (was trivialerweise sortiert ist), und fügt dann benachbarte sortierte Teilarrays zusammen. Der Zusammenführungsschritt ist der Schlüssel: Er verschmilzt zwei sortierte Sequenzen in O(n) Zeit zu einer sortierten Sequenz.
Garantien: Im Gegensatz zu QuickSort ist der schlechteste Fall von Merge Sort immer O(n log n) — er degradiert bei keiner Eingabe. Er ist außerdem stabil (gleiche Elemente behalten ihre ursprüngliche Reihenfolge).
Nachteil: Er benötigt O(n) zusätzlichen Speicher für den temporären Merge-Puffer.
Wann verwenden: Wenn garantiertes O(n log n), Stabilität oder das Sortieren von verketteten Listen gefragt ist. Wird in Javas Arrays.sort für Objekte eingesetzt.