Interaktive Demo
Timsort-Visualisierung
Timsort, 2002 von Tim Peters für Python geschrieben, ist ein Mergesort, der nach Runs sucht: Teilen des Arrays, die schon geordnet sind. Echte Daten enthalten oft solche Runs, und Timsort nutzt sie, statt von vorn zu sortieren.
Wähle „Sortiert“, „Umgekehrt“ oder „Fast sortiert“: Timsort braucht nur wenige Schritte. Die gestrichelten Linien trennen die Runs auf dem Stapel.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Noch in keinem Run
- In einem Run
- Eingefügtes oder kopiertes Element
- Verglichene Anfänge
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n)
Sortierte oder umgekehrte Eingaben sind ein einziger Run: n − 1 Vergleiche und fertig.
Mittlerer Fall
O(n log n)
Kurze Runs werden auf eine Mindestlänge verlängert und dann ausgeglichen gemischt.
Schlechtester Fall
O(n log n)
Die Regeln fürs Mischen halten die Run-Längen ausgeglichen, wie bei Mergesort.
Zusätzlicher Speicher
O(n)
Beim Mischen wird der kürzere von zwei Runs kopiert, höchstens n / 2 Elemente.
Stabil
Ja
Runs werden nur umgedreht, wenn sie streng absteigend sind, und bei Gleichstand bleibt das linke Element vorn.
In-place
Nein
Der kürzere Run wird in ein temporäres Array kopiert.
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
| Algorithmus | Bester Fall | Mittlerer Fall | Schlechtester Fall | Zusätzlicher Speicher | Stabil | In-place |
|---|---|---|---|---|---|---|
| Bubblesort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Selectionsort | O(n²) | O(n²) | O(n²) | O(1) | Nein | Ja |
| Insertionsort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Shellsort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | Nein | Ja |
| Treesort | O(n log n) | O(n log n) | O(n²) | O(n) | Ja | Nein |
| Tournamentsort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Patiencesort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Timsort diese Seite | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Blocksort | O(n) | O(n log n) | O(n log n) | O(1) | Ja | Ja |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) | Nein | Ja |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
1. Runs finden
Timsort läuft durch das Array und findet den nächsten Run. Ein streng absteigender Run wird einfach umgedreht. Ein Run, der kürzer als die Mindestlänge ist, wird mit binärem Insertion Sort verlängert.
2. Den Stapel ausgleichen
Jeder Run kommt auf einen Stapel. Sobald die Run-Längen auf dem Stapel aus dem Gleichgewicht geraten, werden benachbarte Runs gemischt, so bleibt das Mischen etwa so ausgeglichen wie bei Mergesort.
3. Hier vereinfacht
Diese Visualisierung nutzt eine Mindestlänge von 4 (das Original 32 bis 64 und sortiert Arrays unter 64 Elementen allein mit binärem Insertion Sort) und mischt Element für Element. Das Original wechselt außerdem in den „Galopp“, wenn ein Run immer wieder gewinnt, und das aktuelle Python mischt Runs mit der neueren Powersort-Strategie.
Quellen
- Timsort stammt von Tim Peters. Seine Beschreibung des Algorithmus ist listsort.txt im Quellcode von CPython; diese Visualisierung folgt vereinfacht seinen ursprünglichen Regeln fürs Mischen.