Timsort

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 ist ab der Version 2.3 der Standard-Sortieralgorithmus in Python. Mittlerweile wird er auch in Java SE 7 und auf der Android-Plattform genutzt.[1][2]

Funktionsweise

Tim Peters beschreibt den Algorithmus folgendermaßen:

„[…] ein anpassungsfähiges, stabiles Natural Mergesort, das bescheidenerweise Timsort heißt (hey, ich hab's verdient <zwinker>). Es ist leistungsfähiger als Natural Mergesort beim Sortieren von vielen Arten von teilweise sortierten Arrays (weniger als lg(N!) Vergleiche erforderlich, sogar bis hinunter zu N-1), dennoch so schnell wie das von Python vorher eingesetzte, stark optimierte hybride Samplesort beim Sortieren zufälliger Arrays.

Kurz gefasst, geht die Hauptroutine einmal von links nach rechts durch das Array, dabei identifiziert sie abwechselnd die nächste vorsortierte Teilfolge oder fügt diese „intelligent“ mit den vorher erkannten vorsortierten Teilfolgen zusammen. Der Rest dient der Beschleunigung und der hart-erkämpften Verbesserung der Speichereffizienz.“

– Tim Peters[3]

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.[3]

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).[4]

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

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.[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]

Einzelnachweise

  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. ↑ a b Tim 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, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on 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. ↑ a b http://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