Merge Sort Vergleiche

Worum geht es?

Merge Sort teilt das Array rekursiv in zwei Hälften, sortiert diese und führt sie linear zusammen. Die Anzahl Vergleiche beträgt asymptotisch n · log₂(n) — unabhängig von der Eingabereihenfolge.

Vorteile: stabil, garantierte O(n log n)-Laufzeit auch im Worst Case, gut parallelisierbar. Nachteil: benötigt Θ(n) Zusatzspeicher für den Merge-Schritt.

Die Formel

Vergleiche = n · log₂(n)

Rekurrenz:
    T(n) = 2 · T(n / 2) + O(n)

Die Variablen

Minimal-Beispiel

n = 1024:

Vergleiche = 1024 · log₂(1024)
           = 1024 · 10
           = 10 240

Praxis-Beispiele

Beispiel 1 — Eine Million Einträge

Vergleiche = 1 000 000 · log₂(1 000 000)
           ≈ 1 000 000 · 19,93
           ≈ 19 930 000

Beispiel 2 — Vergleich zu Bubble Sort

n = 100 000:

Bubble:  ≈ 5 · 10⁹
Merge:   ≈ 1,7 · 10⁶

Faktor: ca. 3000-fach.

Beispiel 3 — Verdopplung der Eingabe

n: 10⁶ → 2 · 10⁶:

n · log₂(n):
    10⁶ · 20  ≈ 2,0 · 10⁷
2 · 10⁶ · 21  ≈ 4,2 · 10⁷

Etwas mehr als Verdopplung — fast linear.