Sortieralgorithmen: Was Timsort so schnell macht
Beim Aufruf von sort() kümmerte sich von Python Version 2.3 bis 3.11 Timsort darum, Elemente einer Liste in die korrekte Reihenfolge zu manövrieren.
(Bild: Jessica Nachtigall / KI / heise medien)
Wie die Algorithmen Bubblesort, Mergesort und Quicksort Zahlen in Listen sortieren, war Thema im Artikel „Wie Bubblesort, Quicksort und Mergesort funktionieren“. Am Beispiel des langsamen Verfahrens Bubblesort haben wir gezeigt, was die Laufzeit (O-Notation) eines Verfahrens ausmacht. Zudem gingen wir auf Details ein, erklärten, was in-place heißt und was der Unterschied zwischen einem stabilen und einem instabilen Algorithmus ist.
Mit Mergesort und Quicksort demonstrierten wir zwei schnelle Sortieralgorithmen, die beide auf dem Prinzip „Teile und herrsche“ (englisch Divide and Conquer) basieren. Auch wenn Quicksort und Mergesort im Schnitt mit einer Laufzeit von O(n log n) keineswegs langsam sind, so sortieren beide ganz getreu nach ihrem Schema und ignorieren etwa aufsteigende oder absteigende Teilfolgen, die man nicht selten in realen Datensätzen findet.
- Die bisher vorgestellten Verfahren Quicksort, Mergesort und Bubblesort ignorieren sortierte Teilfolgen in Listen.
- Timsort will sich solch vorsortierte Bereiche zunutze machen und kombiniert dazu Binary-Insertionsort und das ZusammenfĂĽhren von Elementen aus Mergesort.
- Timsort weist zwar wie Quicksort und Mergesort eine Laufzeit von O(n log n) auf, erwies sich aber in der Praxis als schneller als die Konkurrenz.
Anstatt einfach ĂĽber sortierte Teilfolgen drĂĽberzubĂĽgeln, macht sich der Sortieralgorithmus Timsort diese zunutze. Den Sortieralgorithmus gibt es erst seit 2002. Lange Zeit nutzte die eingebaute sort()-Funktion vieler Programmiersprachen Timsort.
