Timsort

Überblick

Timsort ist ein hybrider, vergleichsbasierter Sortieralgorithmus, der Verfahren aus Mergesort und Insertionsort verbindet. Er ist anpassungsfähig: Bereits sortierte Bereiche in realen Daten werden erkannt und ausgenutzt. Außerdem ist Timsort stabil, das heißt, Elemente mit gleichem Sortierschlüssel behalten ihre ursprüngliche Reihenfolge.

Tim Peters entwickelte den Algorithmus 2002 für Python. Ab Python 2.3 war Timsort dort der Standard-Sortieralgorithmus, bis er in Python 3.11 durch Powersort ersetzt wurde. Timsort wird außerdem in Java SE 7 und auf der Android-Plattform eingesetzt.

Ablauf des Algorithmus

Timsort durchläuft das Array einmal von links nach rechts und sucht dabei vorsortierte Teilfolgen, sogenannte Abschnitte. Aufsteigend sortierte Abschnitte können direkt verwendet werden; absteigend sortierte Abschnitte werden umgedreht.

Anschließend prüft der Algorithmus, ob jeder gefundene Abschnitt eine von der Array-Größe abhängige Mindestlänge erreicht. Zu kurze Abschnitte werden mithilfe von Insertionsort erweitert. Insertionsort fügt dabei weitere Elemente an der passenden Stelle in den bereits sortierten Teil ein. Sind die Abschnitte lang genug, werden sie nach dem Prinzip von Mergesort schrittweise zu einem vollständig sortierten Array zusammengefügt.

Minimale Abschnittslänge

Bei Arrays mit weniger als 64 Elementen entspricht die minimale Abschnittslänge der Länge des gesamten Arrays. Timsort verhält sich in diesem Fall wie Insertionsort.

Für größere Arrays wird eine Mindestlänge zwischen 32 und 64 bestimmt. Sie wird so gewählt, dass die Array-Länge geteilt durch diese Mindestlänge gleich einer Zweierpotenz oder nur minimal kleiner als eine Zweierpotenz ist. Dazu verwendet der Algorithmus die sechs höchsten Bits der Array-Länge und addiert eins, falls mindestens eines der übrigen Bits gesetzt ist.

Laufzeit und Nutzen vorsortierter Daten

Wie Mergesort besitzt Timsort im besten Fall eine Zeitkomplexität von O(n). Im durchschnittlichen und im schlechtesten Fall beträgt sie O(n log n).

Nach der Informationstheorie benötigt jedes vergleichsbasierte Sortierverfahren im Durchschnitt mindestens Ω(n log n) Vergleiche. Timsort kann auf realen Daten dennoch häufig deutlich weniger Vergleiche benötigen, weil solche Daten oft schon teilweise sortiert sind. Im günstigsten Fall kann die Zahl der Vergleiche bis auf n−1 sinken. Bei zufällig angeordneten Arrays bleibt der Algorithmus ebenfalls schnell.

Fehler in Implementierungen

Im Februar 2015 entdeckte der Amsterdamer Informatiker Stijn de Gouw mithilfe formaler Verifikation einen Fehler in allen damaligen Implementierungen von Timsort. Formale Verifikation bezeichnet den mathematischen Nachweis, dass ein Programm bestimmte Anforderungen erfüllt.

In der Python-Implementierung hatte der Fehler keine praktischen Auswirkungen, weil er nur auf Rechnern mit einer damals nicht vorhandenen, sehr großen Speichermenge auftreten konnte. Er wurde trotzdem behoben, sodass die Korrektheit der Implementierung nachgewiesen werden konnte. Für Java ließ sich dagegen eine Eingabe konstruieren, die das Programm zum Absturz brachte. Auch dieser Fehler wurde kurz nach seiner Bekanntgabe korrigiert.