Komplexität
Das Teilen geht log₂ n Ebenen tief, auf jeder Ebene werden insgesamt n Elemente merged:
Aufwand = n · log₂ n = O(n log n)
| Fall | Komplexität |
|---|
| Worst Case | O(n log n) |
| Average Case | O(n log n) |
| Best Case | O(n log n) |
Klassischer Mergesort hat garantierte O(n log n), egal wie die Eingabe aussieht. Das ist der große Vorteil gegenüber Quicksort.
Adaptive Mergesort-Varianten wie Timsort (Standard in Python und in Java für Arrays.sort(Object[]) seit JDK 7) können auf teilweise sortierten Daten deutlich weniger Vergleiche brauchen als n log n, im Extremfall (sortiert) nahe n. Klassischer Top-down-Mergesort bleibt aber bei n log n. Quelle: Timsort-Originalbeschreibung von Tim Peters und die OpenJDK-Doku zu Arrays.sort().
Eigenschaften
- ✅ Garantierte O(n log n): kein Worst-Case-Risiko
- ✅ Stabil: gleiche Werte behalten ihre relative Reihenfolge
- ✅ Parallelisierbar: Hälften können unabhängig sortiert werden
- ❌ Nicht in-place für Arrays: braucht typischerweise O(n) Zusatzspeicher
Klausur-Trace: Merge-Schritt durchexerziert
Der Merge-Schritt ist das Herzstück und der häufigste Klausur-Stolperfall. Wir mergen zwei bereits sortierte Hälften L = [1, 4, 7] und R = [2, 3, 8] in das Ergebnis-Array T:
| Iter | i (L) | j (R) | L[i] | R[j] | Vergleich | T danach |
|---|
| 1 | 0 | 0 | 1 | 2 | 1 ≤ 2 → nimm L[0] | [1] |
| 2 | 1 | 0 | 4 | 2 | 4 > 2 → nimm R[0] | [1, 2] |
| 3 | 1 | 1 | 4 | 3 | 4 > 3 → nimm R[1] |
5 Vergleiche für 6 Elemente. Im Allgemeinen braucht ein Merge zweier Hälften der Größe n/2 höchstens n-1 Vergleiche.
Wichtig für Stabilität: das ≤ in Zeile "L[i] ≤ R[j] → nimm L[i]" sorgt dafür dass gleiche Werte aus L vor gleichen Werten aus R landen, also Mergesort die ursprüngliche Reihenfolge der gleichen Werte erhält. Mit < statt ≤ wäre Mergesort nicht stabil.
Wann sinnvoll?
- Wenn Stabilität wichtig ist (z.B. Sortieren nach mehreren Kriterien)
- Bei garantierter Performance ohne Worst-Case-Risiko
- Bei verketteten Listen (kein Random-Access nötig, weniger Hilfsspeicher)
- Bei externer Sortierung (Daten passen nicht in den Speicher)
Java-Praxishinweis (Box): In Java unterscheidet sich Arrays.sort() je nach Typ.
Arrays.sort(Object[]) ist stabil und nutzt eine adaptive Mergesort/Timsort-artige Variante.Arrays.sort(int[]) und andere primitive Arrays nutzen Dual-Pivot Quicksort (nicht stabil, Stabilität ist bei Primitiven irrelevant).
