Mergesort.

Mergesort ist ein Sortieralgorithmus nach dem Teile-und-Herrsche-Prinzip. Er halbiert das Array rekursiv, sortiert beide Hälften und verschmilzt sie dann in einem zweiten Schritt zu einem sortierten Ganzen. Garantiert O(n log n) Laufzeit, unabhängig von der Eingabe-Reihenfolge. Du lernst hier die drei Schritte Teile/Sortiere/Merge mit konkretem Trace, warum die Komplexität O(n log n) ist (Master-Theorem: T(n) = 2T(n/2) + O(n) ⇒ O(n log n)), warum Mergesort stabil ist (gleiche Elemente behalten ihre Reihenfolge), warum es typischerweise O(n) Zusatzspeicher braucht (bei Arrays für das Merge-Hilfsarray; bei verketteten Listen kann der Merge-Schritt mit O(1) zusätzlichem Speicher außerhalb des O(log n)-Rekursionsstacks umgesetzt werden), und warum es trotz des Speicher-Overheads als Standard-Sortierverfahren für stabile Sortierung gilt (z. B. Python sorted() mit Timsort, Java Arrays.sort() für Objekt-Arrays).

Was du in der Klausur können musst:

• Idee in 3 Schritten: Teile (Array in der Mitte), Sortiere (beide Hälften rekursiv), Merge (sortiere zusammen)
• Komplexität: O(n log n) im Best-, Average- und Worst-Case
• In-Place: für Array-Mergesort nein, braucht typischerweise O(n) zusätzlichen Speicher für das Merge-Hilfsarray. Bei Linked Lists entfällt das Hilfsarray (Pointer-Umhängen reicht), aber der Rekursionsstack bleibt O(log n). Also: bei Arrays O(n) Hilfsspeicher, bei Linked Lists nur Rekursionsstack.
• Stabil: ja, gleiche Werte behalten ihre Reihenfolge

In Klausuren ist Mergesort oft die Wahl wenn die Aufgabe garantierte O(n log n) oder Stabilität verlangt. Quicksort hat schlechteren Worst-Case (O(n²)), Mergesort braucht aber zusätzlichen Speicher.

Die Idee in 3 Schritten

1. Teile das Array in der Mitte.
2. Sortiere beide Hälften, rekursiv mit Mergesort.
3. Merge die zwei sortierten Hälften zu einem sortierten Ganzen.

Der Merge-Schritt ist der Trick: zwei sortierte Listen lassen sich in O(n) zu einer sortierten Liste verschmelzen, du musst nur immer das kleinere der beiden Köpfe nehmen.

Visualisierung des Teilens

[5, 2, 8, 1, 9, 3, 7, 4]
       ↓ teilen
[5, 2, 8, 1]    [9, 3, 7, 4]
       ↓ teilen
[5, 2] [8, 1]  [9, 3] [7, 4]
       ↓ teilen
[5][2][8][1]  [9][3][7][4]
       ↓ mergen (sortiert)
[2,5] [1,8]  [3,9] [4,7]
       ↓ mergen
[1, 2, 5, 8]   [3, 4, 7, 9]
       ↓ mergen
[1, 2, 3, 4, 5, 7, 8, 9]

Implementierung

public static void mergeSort(int[] arr, int lo, int hi) {
    if (hi - lo <= 1) return;
    int mid = (lo + hi) / 2;
    mergeSort(arr, lo, mid);
    mergeSort(arr, mid, hi);
    merge(arr, lo, mid, hi);
}

private static void merge(int[] arr, int lo, int mid, int hi) {
    int[] tmp = new int[hi - lo];
    int i = lo, j = mid, k = 0;
    while (i < mid && j < hi) {
        tmp[k++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    }
    while (i < mid) tmp[k++] = arr[i++];
    while (j < hi)  tmp[k++] = arr[j++];
    System.arraycopy(tmp, 0, arr, lo, tmp.length);
}

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

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)

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:

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).

Mergesort live

Schau wie Mergesort sein Ergebnis aus immer größeren sortierten Blöcken zusammenbaut. Du siehst die Schreiboperationen, weil jedes Element beim Merge in einen Hilfsarray kopiert und dann zurückgeschrieben wird.

Probier folgendes:

• n = 16: log₂(16) = 4 Halbierungs-Ebenen, ~50 Vergleiche
• n = 32: 5 Ebenen, ~120 Vergleiche
• Jede Verdopplung von n: ~Faktor 2,2 mehr Arbeit (nicht 4×)

Faustregel zum Mitnehmen: Mergesort ist robust. Egal welche Eingabe (zufällig, sortiert, umgekehrt sortiert): immer dieselbe Komplexitätsklasse O(n log n). Konstanten, Implementierung und Cache-Verhalten beeinflussen die konkrete Laufzeit; die asymptotische Klasse bleibt gleich.

---

Code-Stepper: Mergesort mit Call-Stack

Mergesort ist rekursiv. Wir steppen mergeSort([3, 1, 4, 2]) durch und du siehst wie sich der Call-Stack aufbaut, an den Blättern merge aufgerufen wird, und wie die sortierten Teil-Arrays zurück nach oben wandern. Vier Elemente, log₂(4) = 2 Halbierungs-Ebenen.