Interaktive Demo
Mergesort-Visualisierung
Mergesort teilt ein Array so lange in Hälften, bis nur noch einzelne Elemente übrig sind, und mischt die sortierten Hälften dann wieder zusammen. Es ist stabil und braucht immer O(n log n) Schritte, dafür aber ein Hilfsarray.
Klicke auf „Nächster Schritt“, um Schritt für Schritt vorzugehen, oder auf „Abspielen“, um den Algorithmus selbst laufen zu lassen.
Ablauf
Legende
- Unsortiertes Element
- Anfang der linken Teilfolge
- Anfang der rechten Teilfolge
- Im Hilfsarray
- Sortierte Teilfolge
Laufzeit und Eigenschaften
Bester Fall
O(n log n)
Auch sortierte Eingaben werden vollständig geteilt und gemischt: log n Ebenen mit je n Schritten.
Mittlerer Fall
O(n log n)
log n Ebenen durch das Halbieren, und jede Ebene mischt alle n Elemente.
Schlechtester Fall
O(n log n)
Das Halbieren hängt nie von den Werten ab, die Teilung ist also immer ausgeglichen.
Zusätzlicher Speicher
O(n)
Das Mischen braucht ein Hilfsarray so groß wie der gemischte Abschnitt.
Stabil
Ja
Bei Gleichstand wird das Element der linken Teilfolge zuerst genommen.
In-place
Nein
Das Hilfsarray verdoppelt den benötigten Speicher.
n ist die Anzahl der Elemente. O(n log n) ist das Beste, was ein Sortierverfahren auf Basis von Vergleichen erreichen kann.
Im Vergleich mit den anderen Sortieralgorithmen
1. Teilen
Der Abschnitt wird immer wieder in der Mitte geteilt, bis jeder Teil nur noch ein Element enthält und damit schon sortiert ist.
2. Mischen
Zwei sortierte Teilfolgen werden gemischt, indem ihre ersten Elemente verglichen werden und das kleinere ins Hilfsarray wandert. Bei Gleichstand kommt das linke Element zuerst, dadurch bleibt die Sortierung stabil.
3. Zurückkopieren
Die gemischte Folge wird zurück ins Array kopiert. Ebene für Ebene wachsen die sortierten Teilfolgen, bis das ganze Array eine sortierte Folge ist.