Mergesort
Quicksort hat eine unangenehme Eigenschaft: Bei ungünstigen Daten fällt es auf quadratischen Aufwand zurück. Mergesort kennt diesen Fall nicht – es braucht immer n · log n Vergleiche.
Der Preis dafür ist zusätzlicher Speicher.
Die Idee
Mergesort teilt das Feld genau in der Mitte, sortiert beide Hälften rekursiv und verschmilzt die beiden sortierten Hälften anschließend zu einem sortierten Ganzen.
Der Unterschied zu Quicksort liegt in der Verteilung der Arbeit:
| Quicksort | Mergesort | |
|---|---|---|
| Aufwand beim Teilen | hoch (partitionieren) | trivial (Mitte ausrechnen) |
| Aufwand beim Zusammenfügen | keiner | hoch (verschmelzen) |
| Teilung immer gleichmäßig? | nein | ja |
Weil Mergesort immer exakt in der Mitte teilt, gibt es garantiert log n Ebenen – unabhängig von den Daten.
Das Verschmelzen
Der eigentliche Kern des Verfahrens. Zwei sortierte Folgen werden zu einer sortierten zusammengeführt.
Vor dir liegen zwei sortierte Kartenstapel:
links: 1 4 7
rechts: 2 3 9Führe sie auf Papier zusammen: Vergleiche immer nur die beiden obersten Karten und nimm die kleinere.
Notiere jeden Schritt. Wie viele Vergleiche brauchst du?
Auflösung
| Schritt | links | rechts | Vergleich | genommen | Ergebnis |
|---|---|---|---|---|---|
| 1 | 1 4 7 | 2 3 9 | 1 < 2 | 1 | 1 |
| 2 | 4 7 | 2 3 9 | 4 > 2 | 2 | 1 2 |
| 3 | 4 7 | 3 9 | 4 > 3 | 3 | 1 2 3 |
| 4 | 4 7 | 9 | 4 < 9 | 4 | 1 2 3 4 |
| 5 | 7 | 9 | 7 < 9 | 7 | 1 2 3 4 7 |
| 6 | – | 9 | links leer | 9 | 1 2 3 4 7 9 |
Fünf Vergleiche für sechs Elemente. Allgemein braucht das Verschmelzen zweier Folgen mit zusammen n Elementen höchstens n − 1 Vergleiche – jeder Vergleich legt genau ein Element endgültig ab.
Das Verfahren
a) Warum steht das Verschmelzen nach den beiden rekursiven Aufrufen, während bei Quicksort das Partitionieren davor stand?
b) Wofür sind die beiden Schleifen nach der ersten da? Was passiert, wenn man sie weglässt?
c) Warum braucht das Verfahren ein Hilfsfeld?
Auflösung
a) Weil Mergesort die Arbeit beim Zusammenfügen leistet. Vor dem Verschmelzen müssen beide Hälften bereits sortiert sein – also müssen die rekursiven Aufrufe vorher fertig sein.
Bei Quicksort ist es umgekehrt: Dort leistet das Partitionieren die Arbeit, und die Teilbereiche sind danach unabhängig voneinander.
b) Wenn eine Hälfte erschöpft ist, endet die erste Schleife – aber in der anderen liegen noch Elemente. Genau eine der beiden Nachschleifen räumt diesen Rest ab, die andere läuft null Mal.
Ohne sie fehlten Elemente im Ergebnis.
c) Man kann nicht an Ort und Stelle verschmelzen, ohne Werte zu überschreiben, die man noch braucht. Deshalb legt das Verfahren die Ergebnisse zunächst im Hilfsfeld ab und kopiert sie erst am Ende zurück.
Das kostet zusätzlichen Speicher in der Größe des Bereichs – der wesentliche Nachteil gegenüber Quicksort.
Der Ablauf im Bild
Für 5 2 8 1 9 3 7:
5 2 8 1 9 3 7
/ \
5 2 8 1 9 3 7
/ \ / \
5 2 8 1 9 3 7
/ \ / \ / \
5 2 8 1 9 3
────────── ab hier wird verschmolzen ──────────
2 5 1 8 3 9 7
\ / \ /
1 2 5 8 3 7 9
\ /
1 2 3 5 7 8 9Auf dem Hinweg wird nur geteilt, auf dem Rückweg verschmolzen. Es gibt genau ⌈log₂ 7⌉ = 3 Ebenen.
Aufgabe 1: Selbst implementieren
Ergänze die Methoden so, dass alle Tests grün werden.
Fang mit verschmelze an – das ist der schwierige Teil. sortiere ist danach in vier Zeilen geschrieben.
Tipp 1: Drei Zeiger
Du brauchst drei Positionen:
iläuft durch die linke Hälfte, beginnend beipLinks,jdurch die rechte, beginnend beipMitte + 1,kdurch das Hilfsfeld, beginnend bei 0.
Tipp 2: Die Hauptschleife
Solange beide Hälften noch etwas hergeben:
while (i <= pMitte && j <= pRechts) {
if (pWerte[i] <= pWerte[j]) {
hilfe[k] = pWerte[i];
i++;
} else {
hilfe[k] = pWerte[j];
j++;
}
k++;
}Das <= statt < ist wichtig: Bei gleichen Werten wird der linke zuerst genommen. Damit bleibt die ursprüngliche Reihenfolge gleicher Elemente erhalten – man nennt ein solches Verfahren stabil.
Tipp 3: Das Zurückkopieren
Am Ende steht das Ergebnis im Hilfsfeld an den Positionen 0 bis hilfe.length - 1. Im echten Feld gehört es an die Positionen pLinks bis pRechts:
for (int m = 0; m < hilfe.length; m++) {
pWerte[pLinks + m] = hilfe[m];
}Der Versatz um pLinks ist die häufigste Fehlerquelle bei dieser Methode.
Aufgabe 2: Die drei Verfahren im Vergleich
Vergleiche Quicksort, Mergesort und eines der quadratischen Verfahren aus der Einführungsphase.
a) Miss die Vergleichszahlen bei n = 1000, 2000 und 4000 auf zufälligen Daten.
b) Wiederhole die Messung mit bereits sortierten Daten.
c) Fasse die Ergebnisse in einer Tabelle zusammen und beurteile: Welches Verfahren würdest du wofür einsetzen?
Auflösung
| Verfahren | zufällig | sortiert | Zusatzspeicher | Bemerkung |
|---|---|---|---|---|
| Einfügen | n²/4 | n | keiner | bei fast sortierten Daten unschlagbar |
| Quicksort | n·log n | n²/2 | keiner (nur Aufrufstapel) | schnell, aber empfindlich |
| Mergesort | n·log n | n·log n | n | verlässlich, aber speicherhungrig |
Eine vertretbare Empfehlung:
- Kleine oder fast sortierte Datenmengen → Sortieren durch Einfügen.
- Große Datenmengen, Speicher knapp → Quicksort mit guter Pivotwahl.
- Große Datenmengen, Verlässlichkeit wichtig → Mergesort. Es hat keinen schlechten Fall.
- Daten passen nicht in den Arbeitsspeicher → Mergesort. Es ist das einzige der drei, das sich sinnvoll auf Daten anwenden lässt, die stückweise von der Festplatte gelesen werden.
Der letzte Punkt ist der Grund, warum Mergesort trotz des Speicherbedarfs bis heute wichtig ist.
Zusatzaufgabe
Mergesort lässt sich auch iterativ formulieren, ohne Rekursion:
Verschmelze zuerst alle benachbarten Einzelelemente zu Paaren, dann alle benachbarten Paare zu Vierergruppen, dann alle Vierer zu Achtern – und so weiter, bis nur noch ein Block übrig ist.
a) Setze diese Fassung um.
b) Was passiert bei einer Feldlänge, die keine Zweierpotenz ist? Wie musst du damit umgehen?
c) Vergleiche beide Fassungen: Welche findest du verständlicher? Welche braucht weniger Speicher?