Mergesort

Mergesort macht aus einem schweren Problem viele leichte: Zwei sortierte Listen lassen sich einfach zu einer verbinden. Halbieren Sie die Liste, bis jedes Stück ein einzelner Wert ist, und verschmelzen Sie die Stücke dann wieder. Es ist der klassische Teile-und-herrsche-Algorithmus, und seine Laufzeit ist n log n, egal wie die Eingabe aussieht.

Zwei sortierte Hälften einer Liste in einer Pufferzeile, und der kleinere vordere Wert geht zurück hinauf in die Liste
Zwei sortierte Hälften einer Liste in einer Pufferzeile, und der kleinere vordere Wert geht zurück hinauf in die Liste

Die Idee

Das Verschmelzen ist der leichte Teil. Bei zwei Listen, die jeweils sortiert sind, vergleicht man die ersten Werte und nimmt den kleineren. Dann vergleicht man die neuen ersten Werte und nimmt wieder den kleineren. Ist eine Liste leer, hängt man den Rest der anderen an. Jeder Schritt nimmt einen Wert, also braucht das Verschmelzen zweier Listen mit zusammen m Werten höchstens m − 1 Vergleiche. Mergesort nutzt das zum Sortieren: die Liste halbieren, jede Hälfte mit Mergesort sortieren und die beiden Hälften verschmelzen.

Ein Beispiel

Nehmen wir 5, 1, 4, 2, 8. Die Liste wird in 5, 1 und 4, 2, 8 geteilt. Die erste Hälfte wird in 5 und 1 geteilt, die zu 1, 5 verschmelzen. Die zweite Hälfte wird in 4 und 2, 8 geteilt; 2, 8 entsteht durch Verschmelzen von 2 und 8 und wird dann mit 4 zu 2, 4, 8 verschmolzen. Zum Schluss verschmelzen 1, 5 und 2, 4, 8: erst 1, dann 2, dann 4, dann 5, und 8 bleibt übrig. Das sind 8 Vergleiche, 12 Schreibvorgänge und 4 Verschmelzungen.

Warum n log n

Jede Teilung halbiert die Stücke, also ist nach etwa log₂ n Ebenen jedes Stück ein einzelner Wert. Auf dem Rückweg nach oben behandelt jede Ebene von Verschmelzungen jeden Wert einmal: n Schreibvorgänge und weniger als n Vergleiche pro Ebene. Insgesamt sind das etwa n log₂ n. Bei 40 Werten macht die Sortierung 216 Schreibvorgänge und höchstens 177 Vergleiche; Bubblesort kann für dieselbe Liste 780 Vergleiche brauchen. Die Reihenfolge der Eingabe spielt eine viel kleinere Rolle als bei solchen Verfahren: Bei 40 Werten braucht eine sortierte Liste 100 Vergleiche, eine umgekehrte 116 und eine zufällige etwa 160.

Der Puffer und die Stabilität

Um zwei Hälften zu verschmelzen, die in der Liste nebeneinander liegen, kopiert die übliche Methode sie in einen Puffer und schreibt sie geordnet zurück. Die App zeigt diesen Puffer als zweite Balkenreihe. Er braucht so viel zusätzlichen Speicher wie die Liste, das sind die Hauptkosten von Mergesort. Dafür ist die Sortierung stabil: Sind die beiden vorderen Werte gleich, kommt der aus der linken Hälfte zuerst, so behalten gleiche Werte ihre Reihenfolge. Stabilität ist wichtig, wenn man Datensätze nacheinander nach mehreren Feldern sortiert.

Geschichte und Einsatz

John von Neumann beschrieb Mergesort 1945. Damit ist es einer der ersten Algorithmen, die für einen speicherprogrammierten Computer geschrieben wurden. Weil es Daten in langen Folgen liest und schreibt, war es die Standardmethode zum Sortieren von Daten auf Band und wird bis heute für Dateien genutzt, die zu groß für den Arbeitsspeicher sind. Timsort, das Python und, für Objekte, Java verwenden, ist eine Mergesort-Variante, die zuerst bereits sortierte Folgen sucht und für kurze Stücke Insertionsort nutzt.

John von Neumann auf seinem Dienstausweis-Foto aus Los Alamos. 1945 beschrieb er Mergesort, einen der ersten Algorithmen für einen Rechner mit gespeichertem Programm.
John von Neumann auf seinem Dienstausweis-Foto aus Los Alamos. 1945 beschrieb er Mergesort, einen der ersten Algorithmen für einen Rechner mit gespeichertem Programm.

Selbst ausprobieren

Öffnen Sie die App und drücken Sie „Schritt“. Der schattierte Teil der Liste wird gerade geteilt oder verschmolzen, und die gestrichelte Linie markiert die Mitte. Beginnt eine Verschmelzung, fallen beide Hälften in die Pufferzeile; die beiden vorderen Werte werden verglichen, und der kleinere geht wieder hinauf. Achten Sie auf die Zähler: Die Schreibvorgänge sind für jede Liste derselben Länge gleich, und die Vergleiche sind bei einer sortierten oder umgekehrten Liste am niedrigsten und bei einer zufälligen am höchsten, aber nie mehr als etwa n log₂ n.

Häufig gestellte Fragen

Welche Zeitkomplexität hat Mergesort?

O(n log n) im besten, mittleren und schlimmsten Fall. Die übliche Variante braucht O(n) zusätzlichen Speicher für den Puffer.

Was ist der Unterschied zwischen Mergesort und Quicksort?

Beide teilen die Liste und sortieren die Teile. Mergesort teilt in der Mitte, ohne auf die Werte zu schauen, und erledigt die Arbeit beim Verschmelzen; Quicksort erledigt die Arbeit beim Teilen, indem es Werte um ein Pivotelement verschiebt, und braucht kein Verschmelzen. Quicksort sortiert direkt in der Liste und ist in der Praxis oft schneller, kann aber bei ungünstigen Eingaben auf n² abfallen und ist nicht stabil. Mergesort ist immer n log n und stabil.

Was ist Bottom-up-Mergesort?

Eine Variante ohne Rekursion: Zuerst werden benachbarte Einzelwerte zu Paaren verschmolzen, dann Paare zu Vierergruppen und so weiter, wobei sich die Länge jede Runde verdoppelt. Sie leistet dieselbe Arbeit wie die hier gezeigte Top-down-Variante.

Ist Mergesort stabil?

Ja, solange bei Gleichstand zuerst der Wert aus der linken Hälfte genommen wird, wie in dieser App.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Mergesort ausprobieren