Timsort ist ein hybrider Sortieralgorithmus, der von Mergesort und Insertionsort abgeleitet ist. Er wurde entwickelt, um auf verschiedenen realen Daten schnell zu arbeiten. Er wurde 2002 von Tim Peters für die Nutzung in Python entwickelt und war ab der Version 2.3 dort der Standard-Sortieralgorithmus, bis er in Version 3.11 durch Powersort ersetzt wurde. Mittlerweile wird er auch in Java SE 7 und auf der Android-Plattform genutzt.
Funktionsweise Tim Peters beschreibt den Algorithmus folgendermaßen:
Timsort findet bereits sortierte Abschnitte in den Daten. Absteigend sortierte Abschnitte werden umgedreht. Dann wird geprüft, ob die Länge dieser Abschnitte die minimale Abschnittslänge für die jeweilige Array-Größe erreicht. Die minimale Abschnittslänge hängt von der Größe des Arrays ab. Für Arrays mit weniger als 64 Elementen ist die minimale Abschnittslänge das gesamte Array, sodass Timsort in dem Fall einem Insertionsort entspricht. Für größere Arrays wird als minimale Abschnittslänge eine Zahl zwischen 32 und 64 gewählt, sodass die Größe des Arrays geteilt durch die minimale Abschnittslänge gleich einer oder minimal kleiner als eine Zweierpotenz ist. Der Algorithmus nutzt einfach die sechs höchsten Bits der Array-Länge und addiert eins dazu, falls noch zumindest eines der weiteren Bits gesetzt ist. Wenn ein Abschnitt nicht die minimale Abschnittslänge erreicht, wird er mit Insertionsort vergrößert, bis er lang genug ist. Die Abschnitte werden dann mittels Mergesort zum fertig sortierten Array zusammengefügt.
Komplexität und Effizienz
Wie Mergesort ist Timsort ein stabiles, vergleichsbasiertes Sortierverfahren mit einer Best-Case-Komplexität von O(n) und einer Worst- und Average-Case-Komplexität von O(n log n).
Nach der Informationstheorie kann kein vergleichsbasiertes Sortierverfahren mit weniger als Ω(n log n) Vergleichen im Average-Case auskommen. Auf realen Daten braucht Timsort oft deutlich weniger als Ω(n log n) Vergleiche, weil es davon profitiert, dass Teile der Daten schon sortiert sind.
Bekannte Fehler Im Februar 2015 stellte der Amsterdamer Informatiker Stijn de Gouw unter der Verwendung von Methoden zur formalen Verifikation fest, dass alle Implementierungen des Timsort-Algorithmus einen Fehler enthalten.http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ Dieser Fehler hat in der Python-Implementierung keine praktischen Auswirkungen, da er nur auf Rechnern mit sehr viel Speicher auftreten kann, die zurzeit nicht existieren. Dennoch wurde der Fehler behoben, sodass die Korrektheit der Implementierung nachgewiesen werden konnte.http://bugs.python.org/issue23515 Für Java dagegen war die Konstruktion einer Eingabe möglich, die das Programm zum Absturz bringt. Auch hier wurde der Fehler kurz nach Bekanntwerden korrigiert.https://bugs.openjdk.java.net/browse/JDK-8072909
Einzelnachweise
Weblinks Visualising Timsort – Beschreibung mit bildlicher Darstellung Python's listobject.c – die Implementation von Timsort in C für CPython – die Java-Implementation von Timsort
Kategorie:Sortieralgorithmus