Mergesort

• Teilen:den Bereich links … rechts bei mitte halbieren — ohne Vergleich.
• Herrschen:beide Hälften rekursiv mit Mergesort sortieren.
• Zusammenführen:die zwei sortierten Hälften zu einer sortierten Folge mischen (engl. merge).
• Basisfall:Abbruchbedingung: ein Bereich mit höchstens einem Element (links ≥ rechts) ist schon sortiert.
• Mischen:zwei Zeiger i, j auf die Anfänge; das kleinere Element in die Hilfsreihung, dessen Zeiger rückt vor. Ist eine Hälfte leer, kommt der Rest der anderen ohne Vergleich dazu.
• Speicher:eine Hilfsreihung für den gemischten Bereich — Mergesort sortiert nicht in-place.
• Stabil:bei Gleichheit wird zuerst das linke Element genommen (<=).

static void mergesort(int[] a, int links, int rechts) {
    if (links < rechts) {                        // sonst: Basisfall, 0 oder 1 Element
        int mitte = (links + rechts) / 2;
        mergesort(a, links, mitte);              // linke Hälfte sortieren
        mergesort(a, mitte + 1, rechts);         // rechte Hälfte sortieren
        mische(a, links, mitte, rechts);         // beide Hälften mischen
    }
}

static void mische(int[] a, int links, int mitte, int rechts) {
    int[] hilf = new int[rechts - links + 1];
    int i = links, j = mitte + 1, k = 0;
    while (i <= mitte && j <= rechts) {
        if (a[i] <= a[j]) {                      // <= hält gleiche Werte stabil
            hilf[k] = a[i];
            i++;
        } else {
            hilf[k] = a[j];
            j++;
        }
        k++;
    }
    while (i <= mitte) {                         // Rest der linken Hälfte
        hilf[k] = a[i];
        i++;
        k++;
    }
    while (j <= rechts) {                        // Rest der rechten Hälfte
        hilf[k] = a[j];
        j++;
        k++;
    }
    for (k = 0; k < hilf.length; k++) {          // zurückkopieren
        a[links + k] = hilf[k];
    }
}

Beispiel a = {52, 17, 38, 9, 71, 24, 45, 12}: Nach den beiden rekursiven Aufrufen steht links 9, 17, 38, 52, rechts 12, 24, 45, 71. Der letzte Aufruf mische(a, 0, 3, 7) arbeitet so:

Die acht Werte sind schon in Einzelelemente zerlegt. Mische Ebene für Ebene: Klicke die kleinere der beiden hervorgehobenen Karten an (oder ← für die linke, → für die rechte Karte). Der Zähler rechts misst die Vergleiche jeder Ebene. Starte danach mit „Messreihe“ die Messung für größere n.

Halte fest: Jede Ebene kostet höchstens n Vergleiche, und es gibt log₂ n Ebenen. Verdoppelt man n, steigen die Vergleiche nur auf gut das Doppelte — bei Selectionsort auf das Vierfache.