Mergesort

Teilt die Liste in zwei Hälften, sortiert jede Hälfte und führt die beiden sortierten Hälften dann zu einer sortierten Liste zusammen.

bester Fall Ω(n log n)
Durchschnitt Θ(n log n)
schlechtester Fall O(n log n)
Speicher O(n)
stabil
braucht Zusatzspeicher

Was bedeutet das?

Bester Fall: wie die Zeit mit der Listengröße n wächst, wenn die Eingabe für diesen Algorithmus am einfachsten ist.
Durchschnitt: das übliche Wachstum der Zeit mit n. Bei n² dauern doppelt so viele Werte etwa viermal so lang. n log n wächst viel langsamer.
Schlechtester Fall: das Wachstum bei der schwierigsten Eingabe. Wichtig, wenn das Tempo nie einbrechen darf.
Speicher: wie viel Zusatzspeicher neben der Liste nötig ist. 1 heißt ein paar Variablen, n heißt eine Kopie der Liste.
Stabil: Zwei gleiche Werte behalten ihre ursprüngliche Reihenfolge. Wichtig, wenn man Datensätze nach einem Feld sortiert.
Ohne Zusatzspeicher: sortiert direkt in der Liste, ohne zweite Liste.

wird verglichen
wird verschoben
am endgültigen Platz

0 / 263 Schritte

Vergleiche Schreibvorgänge

Auf Abspielen drücken: Die Linien zeigen, wie die Kosten wachsen

Geschwindigkeit 8 Schritte / s

Leertaste: abspielen oder pausieren. Pfeiltasten links/rechts: Schritt. Pos1 und Ende: springen.

Probieren Sie es aus: Wählen Sie wenige unterschiedliche Werte. Bei gleichen Werten wird der aus der linken Hälfte zuerst genommen, so bleibt die Reihenfolge.

So funktioniert es

Die Liste wird so lange geteilt, bis jedes Stück nur noch einen Wert hat. Ein einzelner Wert ist schon sortiert. Dann werden die Stücke paarweise zusammengeführt: Immer wieder wird der kleinere der beiden vordersten Werte genommen. Die angehobene Reihe in der Animation ist der Zusatzspeicher dafür.

Wann es sich eignet

Wenn es auch im schlechtesten Fall schnell bleiben soll und gleiche Werte ihre Reihenfolge behalten müssen. Python und Java nutzen beide eine Variante von Mergesort. Der Nachteil ist der Zusatzspeicher.