Mergesort
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:
izeigt auf die vorderste (kleinste noch verfügbare) Zahl der linken Hälfte.jzeigt auf die vorderste Zahl der rechten Hälfte.kzeigt auf die nächste freie Stelle im Hilfsfeldhilf.
- Es werden immer nur die beiden vordersten Zahlen
feld[i]undfeld[j]miteinander verglichen. - Ist
feld[i] <= feld[j], wird die Zahl aus der linken Hälfte inhilf[k]eingetragen undirückt um 1 weiter. Andernfalls wird die Zahl aus der rechten Hälfte inhilf[k]übernommen undjrückt weiter. In beiden Fällen rücktkauf 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). - 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 mindestens so groß wie alle bisherigen Zahlen sind.
- Zum Schluss wird der Inhalt von
hilfzurück in das ursprünglichefeldkopiert.
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
5und2wird 2 5, aus7und4wird 4 7. Die Paare 1 8 und 3 6 stehen bereits in der richtigen Reihenfolge. - Vierer mischen: Aus
2 5und4 7wird 2 4 5 7. Aus1 8und3 6wird 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
hilfgemischt (grau = bereits verbraucht):i = 0, j = 4: Ist 2 ≤ 1? Nein [math]\displaystyle{ \rightarrow }[/math] 1 ins Hilfsfeld,jrückt weiter. (hilf: 1)i = 0, j = 5: Ist 2 ≤ 3? Ja [math]\displaystyle{ \rightarrow }[/math] 2 ins Hilfsfeld,irückt weiter. (hilf: 1 2)i = 1, j = 5: Ist 4 ≤ 3? Nein [math]\displaystyle{ \rightarrow }[/math] 3 ins Hilfsfeld,jrückt weiter. (hilf: 1 2 3)i = 1, j = 6: Ist 4 ≤ 6? Ja [math]\displaystyle{ \rightarrow }[/math] 4 ins Hilfsfeld,irückt weiter. (hilf: 1 2 3 4)i = 2, j = 6: Ist 5 ≤ 6? Ja [math]\displaystyle{ \rightarrow }[/math] 5 ins Hilfsfeld,irückt weiter. (hilf: 1 2 3 4 5)i = 3, j = 6: Ist 7 ≤ 6? Nein [math]\displaystyle{ \rightarrow }[/math] 6 ins Hilfsfeld,jrückt weiter. (hilf: 1 2 3 4 5 6)i = 3, j = 7: Ist 7 ≤ 8? Ja [math]\displaystyle{ \rightarrow }[/math] 7 ins Hilfsfeld,irückt weiter. (hilf: 1 2 3 4 5 6 7)- 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
hilfkopiert wird: 1 2 3 4 5 6 7 8. Anschließend wirdhilfzurück infeldkopiert.
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 wird üblicherweise die Feldbelegung nach jedem Aufruf von mische angegeben. 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:
| 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 in den hier betrachteten Implementierungen einen Vorgängerzeiger nutzen (zweifach verkettete Liste):
- 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 undendeKnotenist dieser Zugriff überpivotKnoten.getVorgaenger()direkt in [math]\displaystyle{ \mathcal{O}(1) }[/math] möglich. Auf einer einfach verketteten Liste müsste man den Vorgänger jedes Mal vomstartKnotenaus 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 beimstartKnotenneu zu beginnen. - Dabei bezeichnet
startKnotenden ersten undendeKnotenden letzten Knoten der betrachteten Teilliste,pivotKnotenden Pivot-Knoten.getVorgaenger()liefert den Vorgängerknoten,getNaechster()undsetNaechster(...)lesen und setzen den Nachfolger eines Knotens.
- 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
- Warum Mergesort bereits auf einer einfach verketteten Liste ideal arbeitet:
- Reine Vorwärtsnavigation über
naechster: Beim Mischen zweier sortierter Teillisten werden immer nur die vordersten Knoten verglichen und übergetNaechster()in Vorwärtsrichtung weitergeschaltet. Einvorgaenger-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). - Kein Hilfsfeld
hilfnö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 vorhandenennaechster-Zeiger (setNaechster(...)) der Knoten in der sortierten Reihenfolge neu verknüpft. Damit entfällt der Speicher-Nachteil von Mergesort auf verketteten Listen vollständig.
- Reine Vorwärtsnavigation über
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 höchstens [math]\displaystyle{ \lceil \log_2(n) \rceil }[/math]-mal teilen (bei [math]\displaystyle{ n = 8 }[/math] genau [math]\displaystyle{ \log_2(8) = 3 }[/math]-mal, also in 3 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
hilfbenö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.
