Timsort

Timsort visuell dargestellt.

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 von Tim Peters für die Nutzung in Python entwickelt und ist seit der Version 2.3 der Standard-Sortieralgorithmus in Python. Mittlerweile wird er auch in Java SE 7 zum Sortieren von Arrays und auf der Android-Platform genutzt.^[1][2]

Tim Peters beschreibt den Algorithmus folgendermaßen:

„[...] an adaptive, stable, natural mergesort, modestly called timsort (hey, I earned it <wink>). It has supernatural performance on many kinds of partially ordered arrays (less than lg(N!) comparisons needed, and as few as N-1), yet as fast as Python's previous highly tuned samplesort hybrid on random arrays. In a nutshell, the main routine marches over the array once, left to right, alternately identifying the next run, then merging it into the previous runs "intelligently". Everything else is complication for speed, and some hard-won measure of memory efficiency.“

– Tim Peters: ^[3]

Es 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 sie mit Insertionsort vergrößert, bis sie lang genug ist. Die Abschnitte werden dann mittels Mergesort zum fertig sortierten Array zusammengefügt.^[3]

Wie Mergesort ist Timsort ein stabiles, vergleichsbasiertes Sortierverfahren mit einer Best-Case-Komplexität von Θ(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]

Einzelnachweise

1. ↑ jjb: Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort. Java Development Kit 7 Hg repo. Abgerufen am 24 Feb 2011.
2. ↑ Class: java.util.TimSort<T>. Android JDK 1.5 Documentation. Abgerufen am 24 Feb 2011.
3. ↑ ^{a b} Tim Peters: timsort. Python Issue Tracker. Abgerufen am 24 Feb 2011.
4. ↑ Tim Peters: [Python-Dev] Sorting. Python Developers Mailinglist. Abgerufen am 24 Feb 2011. „[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 (In a Nutshell (O'Reilly)). O'Reilly Media, Inc. 2006, ISBN 0596100469

Weblinks

• Visualising Timsort – Die Quelle des Bildes auf dieser Seite
• Python's listobject.c – die Implementation von Timsort in C für CPython
• OpenJDK's TimSort.java – die Java-Implementation von Timsort