~2026-82428-7 am 6. Februar 2026 um 16:12 Uhr

2026-02-06T16:12:25Z

Neue Seite

'''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 (Programmiersprache)|Python]] entwickelt und war ab der Version 2.3 dort der Standard-Sortieralgorithmus, bis er in Version 3.11 durch [[Powersort]] ersetzt wurde.<ref>{{Internetquelle |autor=Sebastian Wild |url=https://www.wild-inter.net/posts/powersort-in-python-3.11 |titel=Powersort in official Python 3.11 release |werk=wild-inter.net |datum=2022-10-24 |sprache=en |abruf=2026-02-04}}</ref> Mittlerweile wird er auch in [[Java SE]] 7 und auf der [[Android (Betriebssystem)|Android-Plattform]] genutzt.<ref>{{Internetquelle |autor=jjb |url=http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79 |titel=Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort |werk=Java Development Kit 7 Hg repo |sprache=en |abruf=2011-02-24 |offline=ja |archiv-bot=2024-05-29 23:10:47 InternetArchiveBot |archiv-url=https://web.archive.org/web/20120228192950/http://hg.openjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79 |archiv-datum=2012-02-28 }}</ref><ref>{{Internetquelle |url=http://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort |titel=Class: java.util.TimSort<T> |werk=Android JDK 1.5 Documentation |sprache=en |abruf=2011-02-24}}</ref>

== Funktionsweise ==
Tim Peters beschreibt den Algorithmus folgendermaßen:

{{Zitat|[…] 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 [[Array (Datentyp)|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 [[Effizienz (Informatik)|Speichereffizienz]].
|Autor=Tim Peters
|ref=<ref name="timsort.txt">{{Internetquelle |autor=Tim Peters |url=https://bugs.python.org/file4451/timsort.txt |titel=timsort |werk=Python Issue Tracker |sprache=en |abruf=2011-02-24}}</ref>
}}

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 [[Bit]]s 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.<ref name="timsort.txt" />

== Komplexität und Effizienz ==

Wie Mergesort ist Timsort ein [[Stabilität (Sortierverfahren)|stabiles]], [[vergleichsbasiertes Sortierverfahren]] mit einer Best-Case-[[Zeitkomplexität|Komplexität]] von [[Landau-Symbole|O]](''n'') und einer Worst- und Average-Case-Komplexität von O(''n'' log ''n'').<ref>{{Internetquelle |autor=Tim Peters |titel=[Python-Dev] Sorting |url=https://mail.python.org/pipermail/python-dev/2002-July/026837.html |werk=Python Developers Mailinglist |datum=2002-07-20 |sprache=en |abruf=2011-02-24 |zitat=[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).}}</ref>

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.<ref>{{Literatur |Autor=Alex Martelli |Titel=Python in a Nutshell |Verlag=O’Reilly |Datum=2006 |Seiten=57 |ISBN=0596100469}}</ref>

== Bekannte Fehler ==
Im Februar 2015 stellte der Amsterdamer Informatiker Stijn de Gouw unter der Verwendung von Methoden zur [[Formale Verifikation|formalen Verifikation]] fest, dass alle Implementierungen des Timsort-Algorithmus einen Fehler enthalten.<ref name=":0">http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/</ref> 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.<ref>http://bugs.python.org/issue23515</ref><ref name=":0" /> 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.<ref>https://bugs.openjdk.java.net/browse/JDK-8072909</ref>

== Einzelnachweise ==
<references />

== Weblinks ==
* [https://corte.si/posts/code/timsort/index.html Visualising Timsort] – Beschreibung mit bildlicher Darstellung
* [https://svn.python.org/projects/python/trunk/Objects/listobject.c Python's listobject.c] – die Implementation von Timsort in [[C (Programmiersprache)|C]] für [[CPython]]
* {{GitHub|openjdk/jdk/blob/master/src/java.base/share/classes/java/util/TimSort.java|OpenJDK's TimSort.java}} – die Java-Implementation von Timsort

[[Kategorie:Sortieralgorithmus]]

Timsort - Versionsgeschichte

~2026-82428-7 am 6. Februar 2026 um 16:12 Uhr