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.
- Ω(n log n)
- Θ(n log n)
- O(n log n)
- O(n)
- ja
- nein
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
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.