Timsort ist ein hybriderSortieralgorithmus, der vonMergesort undInsertionsort abgeleitet ist. Er wurde entwickelt, um auf verschiedenen realen Daten schnell zu arbeiten. Er wurde 2002 von Tim Peters für die Nutzung inPython entwickelt und ist ab der Version 2.3 der Standard-Sortieralgorithmus in Python. Mittlerweile wird er auch inJava SE 7 und auf derAndroid-Plattform genutzt.^[1][2]

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 eineZweierpotenz ist. Der Algorithmus nutzt einfach die sechs höchstenBits 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.^[3]

Wie Mergesort ist Timsort einstabiles,vergleichsbasiertes Sortierverfahren mit einer Best-Case-Komplexität vonO(n) und einer Worst- und Average-Case-Komplexität von O(n log n).^[4]

Nach derInformationstheorie 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.^[5]

Im Februar 2015 stellte der Amsterdamer Informatiker Stijn de Gouw unter der Verwendung von Methoden zurformalen Verifikation fest, dass alle Implementierungen des Timsort-Algorithmus einen Fehler enthalten.^[6] 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.^[7][6] 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.^[8]

1. ↑jjb: Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort. In: Java Development Kit 7 Hg repo. Archiviert vom Original (nicht mehr online verfügbar) am 28. Februar 2012; abgerufen am 24. Februar 2011 (englisch).  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäßAnleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/hg.openjdk.java.net 
2. ↑Class: java.util.TimSort<T>. In: Android JDK 1.5 Documentation. Abgerufen am 24. Februar 2011 (englisch). 
3. ↑^abTim Peters: timsort. In: Python Issue Tracker. Abgerufen am 24. Februar 2011 (englisch). 
4. ↑Tim Peters: [Python-Dev] Sorting. In: Python Developers Mailinglist. 20. Juli 2002, abgerufen am 24. Februar 2011 (englisch): „[Timsort] also has good aspects:It's stable (items that compare equal retain their relative order, so,e.g., if you sort first on zip code, and a second time on name, peoplewith the same name still appear in order of increasing zip code; thisis important in apps that, e.g., refine the results of queries basedon user input)....It has no bad cases (O(N log N) is worst case; N-1 compares is best).“ 
5. ↑Alex Martelli:Python in a Nutshell. O’Reilly, 2006,ISBN 0-596-10046-9,S. 57. 
6. ↑^abhttp://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
7. ↑http://bugs.python.org/issue23515
8. ↑https://bugs.openjdk.java.net/browse/JDK-8072909

• Visualising Timsort – Beschreibung mit bildlicher Darstellung
• Python's listobject.c – die Implementation von Timsort inC fürCPython
• OpenJDK's TimSort.java aufGitHub – die Java-Implementation von Timsort

• Sortieralgorithmus

• Wikipedia:Defekte Weblinks/Ungeprüfte Archivlinks 2024-05