InsertionSort und MergeSort

InsertionSort und MergeSort sind zwei wichtige Sortieralgorithmen, die im Hessen-Abitur verglichen werden. InsertionSort sortiert ähnlich wie das Aufnehmen von Spielkarten in eine geordnete Hand und ist mit \( \mathcal{O}(n^2) \) ein klassisches quadratisches Verfahren. MergeSort dagegen nutzt das Prinzip Divide and Conquer und erreicht \( \mathcal{O}(n \log n) \) – das macht ihn zu einem der schnellsten allgemein verwendbaren Sortieralgorithmen.

Bei InsertionSort wird das Array von links nach rechts durchlaufen. Jedes neue Element wird in den bereits sortierten linken Teil einsortiert, indem größere Elemente eine Position nach rechts verschoben werden.

Java-Implementierung:

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

Python-Implementierung:

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key

MergeSort zerlegt das Array rekursiv in zwei Hälften, sortiert diese einzeln und führt sie anschließend wieder geordnet zusammen (Schritt Merge). Die Rekursion endet bei Teilfolgen der Länge 1, die per Definition sortiert sind.

Java-Implementierung:

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

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

Python-Implementierung:

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[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

InsertionSort hat im schlechtesten Fall (umgekehrt sortiert) \( \mathcal{O}(n^2) \) Vergleiche, im besten Fall (bereits sortiert) nur \( \mathcal{O}(n) \). MergeSort benötigt \( \log_2 n \) Rekursionsstufen, in jeder werden \( n \) Elemente verglichen und kopiert – das ergibt \( \mathcal{O}(n \log n) \) in jedem Fall. MergeSort ist stabil, benötigt aber zusätzlichen Speicher der Größe \( \mathcal{O}(n) \).

InsertionSort eignet sich für kleine oder fast sortierte Arrays. MergeSort wird in Standardbibliotheken (z. B. Java Arrays.sort für Objekte) eingesetzt. Häufige Fehler: Bei InsertionSort wird die Schleife ab Index 0 statt 1 gestartet; bei MergeSort werden die Indizes mid und mid + 1 falsch abgegrenzt, sodass Elemente verloren gehen oder doppelt sortiert werden.

Zusammenfassung: InsertionSort ist einfach und für kleine Daten brauchbar (\( \mathcal{O}(n^2) \)). MergeSort nutzt Divide and Conquer und erreicht durch rekursive Halbierung \( \mathcal{O}(n \log n) \).

Abitur-Tipp: Zeichne für MergeSort den Rekursionsbaum und markiere darin die Merge-Schritte. So erkennt man visuell die \( \log_2 n \) Stufen.