Einführung

Ein in der Praxis häufig eingesetzter, sehr effizienter und im Gegensatz zu Quicksort auch stabiler Sortieralgorithmus ist der Mergesort (Sortieren durch Mischen). Er funktioniert nach dem Prinzip „Teile und herrsche“ (Divide and Conquer), bei dem aus einem großen Problem zwei kleinere Teilprobleme gemacht werden, was in der Programmierung mithilfe von Rekursion umgesetzt wird.

Die Grundidee gliedert sich in zwei Phasen:

  • Teilen: Das zu sortierende Feld wird fortlaufend in der Mitte in zwei Hälften geteilt, bis jedes Teilfeld nur noch aus einer einzigen Zahl besteht. Da eine einzelne Zahl für sich genommen immer sortiert ist, endet hier das Teilen (Abbruch der Rekursion).
  • Mischen: Anschließend geht der Algorithmus den Weg wieder zurück und mischt jeweils zwei benachbarte, bereits sortierte Teilfelder Schritt für Schritt zu einem doppelt so großen, sortierten Teilfeld zusammen.

Während Quicksort die Hauptarbeit bereits beim Aufteilen (Partitionieren) leistet, ist das Teilen bei Mergesort denkbar einfach – die eigentliche Sortierarbeit steckt im Mischen.

Wie funktioniert das Mischen?

Liegen zwei benachbarte, bereits sortierte Hälften in einem Array (feld) vor, werden diese mit Hilfe eines temporären Hilfsfelds (hilf) und dreier Zeiger zusammengeführt:

  • i zeigt auf die vorderste (kleinste noch verfügbare) Zahl der linken Hälfte.
  • j zeigt auf die vorderste Zahl der rechten Hälfte.
  • k zeigt auf die nächste freie Stelle im Hilfsfeld hilf.
  1. Es werden immer nur die beiden vordersten Zahlen feld[i] und feld[j] miteinander verglichen.
  2. Ist feld[i] <= feld[j], wird die Zahl aus der linken Hälfte in hilf[k] eingetragen und i rückt um 1 weiter. Andernfalls wird die Zahl aus der rechten Hälfte in hilf[k] übernommen und j rückt weiter. In beiden Fällen rückt k auf die nächste freie Stelle. (Durch das <= wird bei gleichen Zahlen stets die linke Zahl zuerst übernommen – dadurch bleibt die Reihenfolge gleicher Elemente erhalten und Mergesort ist stabil).
  3. Sobald eine der beiden Hälften vollständig verbraucht ist, wird der Rest der anderen Hälfte ohne weitere Vergleiche hinten an das Hilfsfeld angehängt, da diese Zahlen bereits sortiert und größer als alle bisherigen Zahlen sind.
  4. Zum Schluss wird der Inhalt von hilf zurück in das ursprüngliche feld kopiert.

Beispiel

Wir betrachten acht unsortierte Lieferscheine in einem Feld: 5, 2, 7, 4, 1, 8, 3, 6.

1. Teilen (von oben nach unten)

Das Feld wird schrittweise in der Mitte halbiert, bis nur noch einzelne Zahlen übrig bleiben:

  • Start (8 Lieferscheine): 5 2 7 4 1 8 3 6
  • Hälften (je 4 Zahlen): 5 2 7 4  |  1 8 3 6
  • Viertel (je 2 Zahlen): 5 2  |  7 4   und   1 8  |  3 6
  • Einzelne Zahlen (je 1 Zahl – immer sortiert): 5 | 2 | 7 | 4 | 1 | 8 | 3 | 6

2. Mischen (von unten nach oben)

Nun werden jeweils zwei benachbarte Teile sortiert zusammengemischt:

  • Paare mischen: Aus 5 und 2 wird 2 5, aus 7 und 4 wird 4 7. Die Paare 1 8 und 3 6 stehen bereits in der richtigen Reihenfolge.
  • Vierer mischen: Aus 2 5 und 4 7 wird 2 4 5 7. Aus 1 8 und 3 6 wird 1 3 6 8.
  • Letztes Mischen zum sortierten Feld: Die beiden sortierten Hälften 2 4 5 7 (Index 0 bis 3) und 1 3 6 8 (Index 4 bis 7) werden in das Hilfsfeld hilf gemischt (grau = bereits verbraucht):
    1. i = 0, j = 4: Ist 2 ≤ 1? Nein [math]\displaystyle{ \rightarrow }[/math] 1 ins Hilfsfeld, j rückt weiter. (hilf: 1)
    2. i = 0, j = 5: Ist 2 ≤ 3? Ja [math]\displaystyle{ \rightarrow }[/math] 2 ins Hilfsfeld, i rückt weiter. (hilf: 1 2)
    3. i = 1, j = 5: Ist 4 ≤ 3? Nein [math]\displaystyle{ \rightarrow }[/math] 3 ins Hilfsfeld, j rückt weiter. (hilf: 1 2 3)
    4. i = 1, j = 6: Ist 4 ≤ 6? Ja [math]\displaystyle{ \rightarrow }[/math] 4 ins Hilfsfeld, i rückt weiter. (hilf: 1 2 3 4)
    5. i = 2, j = 6: Ist 5 ≤ 6? Ja [math]\displaystyle{ \rightarrow }[/math] 5 ins Hilfsfeld, i rückt weiter. (hilf: 1 2 3 4 5)
    6. i = 3, j = 6: Ist 7 ≤ 6? Nein [math]\displaystyle{ \rightarrow }[/math] 6 ins Hilfsfeld, j rückt weiter. (hilf: 1 2 3 4 5 6)
    7. i = 3, j = 7: Ist 7 ≤ 8? Ja [math]\displaystyle{ \rightarrow }[/math] 7 ins Hilfsfeld, i rückt weiter. (hilf: 1 2 3 4 5 6 7)
    8. Rest anhängen: Links ist nach 7 Vergleichen alles verbraucht (2 4 5 7). Rechts liegt noch die 8, die ohne Vergleich ans Ende von hilf kopiert wird: 1 2 3 4 5 6 7 8. Anschließend wird hilf zurück in feld kopiert.

Typischer Fehler – Rest vergessen: Wird nach der Hauptschleife vergessen, die übrig gebliebenen Zahlen der noch nicht geleerten Hälfte in das Hilfsfeld zu übertragen, steht am Ende 1 2 3 4 5 6 7 0 im Feld, da ein neu angelegtes int-Feld in Java standardmäßig mit Nullen vorinitialisiert ist.

Java Implementierung

Die Implementierung besteht aus zwei Methoden: mergeSort steuert die rekursive Teilung über die Bereichsgrenzen links und rechts, während mische die beiden sortierten Teilbereiche [links ... mitte] und [mitte + 1 ... rechts] zusammenführt. Gestartet wird die Sortierung für das gesamte Feld mit dem Aufruf mergeSort(feld, 0, feld.length - 1);.

static void mergeSort(int[] feld, int links, int rechts) {
    if (links < rechts) {
        int mitte = (links + rechts) / 2;
        mergeSort(feld, links, mitte);
        mergeSort(feld, mitte + 1, rechts);
        mische(feld, links, mitte, rechts);
    }
}

static void mische(int[] feld, 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 (feld[i] <= feld[j]) {
            hilf[k] = feld[i];
            i++;
        } else {
            hilf[k] = feld[j];
            j++;
        }
        k++;
    }

    // Rest der linken bzw. rechten Hälfte übernehmen
    while (i <= mitte)  { hilf[k] = feld[i]; i++; k++; }
    while (j <= rechts) { hilf[k] = feld[j]; j++; k++; }

    // Zurück ins Feld kopieren (ab Index links)
    for (k = 0; k < hilf.length; k++) {
        feld[links + k] = hilf[k];
    }
}

Schreibtischtest (Reihenfolge der Aufrufe)

Bei einem Schreibtischtest im Abitur muss die Feldbelegung nach jedem Aufruf von mische angegeben werden. Wichtig: Java arbeitet den Rekursionsbaum nicht Ebene für Ebene ab, sondern steigt durch den ersten rekursiven Aufruf mergeSort(feld, links, mitte) zuerst in der linken Hälfte komplett in die Tiefe ab, bevor die rechte Hälfte betrachtet wird:

Chronologische Reihenfolge der 7 mische-Aufrufe für 5 2 7 4 1 8 3 6
Nr. Aufruf feld nach dem Aufruf Anzahl Vergleiche
1. mische(0, 0, 1) 2 5 7 4 1 8 3 6 1
2. mische(2, 2, 3) 2 5 4 7 1 8 3 6 1
3. mische(0, 1, 3) 2 4 5 7 1 8 3 6 3
4. mische(4, 4, 5) 2 4 5 7 1 8 3 6 1
5. mische(6, 6, 7) 2 4 5 7 1 8 3 6 1
6. mische(4, 5, 7) 2 4 5 7 1 3 6 8 3
7. mische(0, 3, 7) 1 2 3 4 5 6 7 8 7
Summe der Vergleiche: 17

Mergesort auf verketteten Listen

Während auf einem Array oft Quicksort bevorzugt wird, weil Mergesort dort ein zusätzliches Hilfsfeld hilf benötigt, ist Mergesort das optimale Sortierverfahren für verkettete Listen – insbesondere schon für einfach verkettete Listen, deren Knoten lediglich eine Referenz naechster auf den Nachfolger, aber keinen Verweis vorgaenger besitzen:

  • Warum Quicksort und Insertion Sort eine zweifach verkettete Liste benötigen:
    • Bei Quicksort wird für den rekursiven Aufruf der linken Teilliste der Knoten unmittelbar vor dem Pivot-Knoten als neue rechte Grenze benötigt. Nur in einer bidirektionalen (zweifach verketteten) Liste mit vorgaenger-Zeiger und endeKnoten ist dieser Zugriff über pivotKnoten.getVorgaenger() direkt in [math]\displaystyle{ \mathcal{O}(1) }[/math] möglich. Auf einer einfach verketteten Liste müsste man den Vorgänger jedes Mal vom startKnoten aus in [math]\displaystyle{ \mathcal{O}(n) }[/math] suchen.
    • Auch Insertion Sort profitiert stark von einer Doppelverkettung, da der Suchzeiger über getVorgaenger() direkt vom aktuellen Element aus rückwärts durch den sortierten Bereich wandern kann, statt jedes Mal beim startKnoten neu zu beginnen.
  • Warum Mergesort bereits auf einer einfach verketteten Liste ideal arbeitet:
    1. Reine Vorwärtsnavigation über naechster: Beim Mischen zweier sortierter Teillisten werden immer nur die vordersten Knoten verglichen und über getNaechster() in Vorwärtsrichtung weitergeschaltet. Ein vorgaenger-Zeiger bringt für Mergesort keinen Vorteil, weil niemals rückwärts navigiert werden muss. Auch die Listenmitte lässt sich vorwärts bestimmen (ein langsamer Zeiger rückt einen Knoten weiter, ein schneller Zeiger zwei Knoten).
    2. Kein Hilfsfeld hilf nötig ([math]\displaystyle{ \mathcal{O}(1) }[/math] Zusatzspeicher für Knoten): Auf einer verketteten Liste müssen beim Mischen keine neuen Knoten im Speicher angelegt und keine Daten in ein Hilfsfeld kopiert werden. Stattdessen werden einfach die vorhandenen naechster-Zeiger (setNaechster(...)) der Knoten in der sortierten Reihenfolge neu verknüpft. Damit entfällt der Speicher-Nachteil von Mergesort auf verketteten Listen vollständig.

Laufzeitanalyse

Für die Laufzeitanalyse betrachten wir die Anzahl der Teilungsebenen und die Anzahl der Vergleiche pro Ebene:

  • Anzahl der Ebenen: Da das Feld in jedem Schritt halbiert wird ([math]\displaystyle{ 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 }[/math]), lässt sich ein Feld mit [math]\displaystyle{ n }[/math] Zahlen genau [math]\displaystyle{ \log_2(n) }[/math]-mal teilen (bei [math]\displaystyle{ n = 8 }[/math] sind es [math]\displaystyle{ \log_2(8) = 3 }[/math] Ebenen).
  • Vergleiche pro Ebene: Auf jeder Ebene wird mit jedem Vergleich genau eine Zahl in das Hilfsfeld übertragen. Für [math]\displaystyle{ n }[/math] Zahlen sind pro Ebene also höchstens [math]\displaystyle{ n }[/math] Vergleiche nötig.

Multipliziert man die [math]\displaystyle{ \log_2(n) }[/math] Ebenen mit höchstens [math]\displaystyle{ n }[/math] Vergleichen pro Ebene, benötigt Mergesort insgesamt höchstens [math]\displaystyle{ n \cdot \log_2(n) }[/math] Vergleiche (bei [math]\displaystyle{ n = 8 }[/math] höchstens [math]\displaystyle{ 8 \cdot 3 = 24 }[/math] Vergleiche, in unserem Beispiel tatsächlich [math]\displaystyle{ 17 }[/math]).

Da Mergesort das Feld unabhängig von den gespeicherten Zahlen immer stur in der Mitte teilt, kann der Aufrufbaum niemals wie bei Quicksort entarten:

  • Best-Case, Average-Case und Worst-Case: In allen drei Fällen beträgt die Zeitkomplexität garantiert [math]\displaystyle{ \mathcal{O}(n \cdot \log n) }[/math].
  • Platzkomplexität: Auf einem Array wird zusätzlicher Speicher in [math]\displaystyle{ \mathcal{O}(n) }[/math] für das Hilfsfeld hilf benötigt (nicht In-Place). Auf einer verketteten Liste werden nur Zeiger umgebogen, sodass kein Hilfsfeld nötig ist.

Laufzeitvergleich: Bubblesort vs. Mergesort

Der enorme Geschwindigkeitsvorteil von [math]\displaystyle{ \mathcal{O}(n \cdot \log n) }[/math] gegenüber quadratischen Verfahren wie Bubblesort ([math]\displaystyle{ \mathcal{O}(n^2) }[/math] mit [math]\displaystyle{ \frac{n(n-1)}{2} }[/math] Vergleichen) zeigt sich besonders bei großen Datenmengen:

Anzahl Elemente [math]\displaystyle{ n }[/math] Bubblesort
[math]\displaystyle{ \frac{n(n-1)}{2} }[/math] Vergleiche
Mergesort
höchstens [math]\displaystyle{ n \cdot \log_2(n) }[/math] Vergleiche
8 28 24 (im Beispiel 17)
1.000 499.500 [math]\displaystyle{ \approx }[/math] 10.000
1.000.000 [math]\displaystyle{ \approx }[/math] 500 Mrd. [math]\displaystyle{ \approx }[/math] 20 Mio.

Rechenbeispiel: Ein Rechner, der 1 Milliarde Vergleiche pro Sekunde ausführt, benötigt für eine Million Zahlen mit Bubblesort gut 8 Minuten, mit Mergesort hingegen nur 0,02 Sekunden.