UniProMax/Algorithmen/mergesort

Mergesort

Teile und Herrsche. Garantierte O(n log n) durch rekursives Halbieren plus Merge. Stabil, aber braucht O(n) Zusatzspeicher. Klausur-Klassiker schlechthin.

3LerneinheitenVoraussetzungen:Big-O Notation

Relevant für:Informatik(Klausurniveau)Wirtschaftsinformatik(Grundlagen)Data Science(Grundlagen)

Sprache wählen

Sprache

Lerneinheit 1 von 3java + python

Mergesort

Der schlaue Sortieralgorithmus. Klassischer Teile-und-Herrsche-Ansatz (Divide & Conquer).

Die Idee in 3 Schritten

Teile das Array in der Mitte.
Sortiere beide Hälften, rekursiv mit Mergesort.
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

java// snippet

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);
}

Java: rekursives Splitten plus Merge in einen Hilfsarray. Aufruf: mergeSort(arr, 0, arr.length).

Komplexität

Das Teilen geht $\log_2 n$ Ebenen tief, auf jeder Ebene werden insgesamt $n$ Elemente merged:

$\text{Aufwand} = n \cdot \log_2 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)$

Mergesort hat garantierte $O(n \log n)$ , egal wie die Eingabe aussieht. Das ist der große Vorteil gegenüber Quicksort.

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: braucht O(n) Zusatzspeicher

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)
Bei externer Sortierung (Daten passen nicht in den Speicher)

Java's Arrays.sort() für Objekte nutzt eine Mergesort-Variante (Timsort).

VorkenntnisBig-O Notation Baut darauf aufQuicksort