24.06.2020
Hier klicken um den Array sortiert zu zeigenHier klicken um neue Zufallszahlen zu laden 

Algorithmus: Timsort

Timsort ist ein hybrider Sortieralgorithmus, der von Tim Peters für die Sprache Python entwickelt wurde, jetzt aber auch unter anderem in Java und Android genutzt wird. Hybrid bedeutet dass mehrere Sortiertechniken in einem Algorithmus kombiniert werden, um bessere Leistung bei echten Daten zu erreichen. Die Hauptzutaten sind Insertionsort und Mergesort. Aber Timsort hat auch eine Technik um existierende Läufe (engl. runs) im Eingabearray zu finden und zu nutzen.

Das obige Panel zeigt ein zufälliges Array bei dem Läufe fabrig markiert sind. Wir haben den Zufallsgenerator ein bisschen modifiziert, damit mehrere und längere Läufe vorkommen als bei rein zufälligen Daten. Läufe sind also existierene Abschnitte in den Daten, die bereits sortiert sind. Aufsteigende Läufe sind grün markiert, und absteigende Läufe sind rot dargestellt. Solche Läufe sind oft in realen Arrays schon vorhanden, je nachdem welche Art Daten vorliegen. In manchen Fällen sind es wirklich nur einige wenige Werte die noch nicht an die richtige Stelle sortiert sind.


slowerplaypausefaster

Läufe finden

Dieses Panel zeigt wie die Läufe gefunden werden. Es ist ein ziemlich einfacher Schritt: man vergleiche einfach das nächste Element mit dem vorherigen und stellt fest ob es Teil eines existierenden Laufes ist, oder ob der Lauf zu Ende kommt. Die dicken Striche im Array zeigen die Grenzen der Läufe an.


slowerplaypausefaster

Läufe umkehren

Sobald die Läufe identifiziert sind, gibt es einen weiteren einfachen und schnellen Schritt: alle Läufe die entgegen der gewünschten Sortierrichtung laufen müssen umgekehrt werden. In diesem Fall wollen wir die absteigenden Läufe umkehren. Das Panel zeigt ein Array bei dem die Läufe bereits markiert sind und kehrt die absteigenden Läufe um. Man beachte, dass in absteigenden Läufen, aufeinanderfolgende aber gleiche Werte nicht zum selben Lauf gerechnet werden sollen. Dies ist der erste Schritt im Algorithmus, der Timsort zu einem ‘stabilen’ Sortierverfahren macht, bei dem also eine bereits vorhandene Ordnung bei gleichen Werten nicht verändert wird. Weil absteigende Läufe umgedreht werden, können sie also keine gleichen Werte enthalten.


Bereit zum SortierenLäufe findenLäufe umkehrenLäufe zusammenführenSortierung abgeschlossen 
 
slowerplaypausefaster

Natürliches Mergesort

An diesem Punkt ist es möglich, das ganze Array zu sortieren, ohne weitere Timsort-Magie, einfach indem unsortierte Abschnitte mit den Läufen zusammengeführt werden. Dies nennt man ‘natürliches Mergesort’. Es wird auf diesem Panel dargestellt, beginnend mit einem unsortierten Array werden Läufe gefunden und evtl. umgedreht, bis alle Läufe zusammengeführt worden sind und das Array sortiert ist. Dies war aber nur eine Nebenbemerkung, jetzt geht es mit Timsort weiter, ab dem Umkehren der Läufe.


Bereit zum SortierenLauf findenLauf umkehrenInsertionsort am LaufSchritte abgeschlossen 
 
slowerplaypausefaster

Minrun

Timsort hat einen Parameter namens ‘minrun’. Dies ist die minimale Größe die ein Lauf haben sollte bevor der nächste Schritt ausgeführt wird, dem Zusammenführen der Läufe. Diese Mindestgröße wird erfüllt indem Insertionsort auf den Lauf ausgeführt wird, die folgenden Elemente also in den Lauf eingefügt werden, bis die Minimalgröße erreicht ist. Dies ist sehr effizient, weil Insertionsort auf kurzen Eingaben schnell läuft.

Minrun wird zu Beginn des Algorithmus als Funktion der Länge der Eingabe berechnet, und ist mindestens 32. Hier wurde der Wert aber auf 11 reduziert, um die Arbeitsweise von Timsort auf den kurzen Arrays die wir hier darstellen können, zu zeigen. Der letzte Lauf kann natürlich weniger als minrun Elemente enthalten.


Bereit zum SortierenLauf findenLauf umkehrenInsertionsort am LaufMergen hochMergen tiefSortierung abgeschlossen 
 
slowerplaypausefaster

Timsort

Hier sehen wir den gesamten Ablauf von Timsort auf einem größeren Array von 71 Werten, zur besseren Illustration. Nach dem Finden, Umkehren und der möglichen Anwendung von Insertionsort um die Größe auf mindestens minrun (= 11) zu erhöhen, wird der letzte Schritt von Timsort ausgeführt: Mergen. Ein Stack (dt. Stapel), der hier unten rechts gezeigt wird, speichert die Positionen der Läufe, in der Reihenfolge in der sie im Array vorkommen. Sobald neue Läufe dazukommen, werden sie oben in den Stack gestellt.

Timsort bewahrt zwei Invarianten auf dem Stack: die Summe der Längen der letzten beiden Läufe muss kürzer sein als der davorige Lauf, und die Länge des letzten Eintrags muss kürzer sein als sein Vorgänger. Sobald einer dieser Invarianten ungültig ist, führt dies dazu dass benachbarte Läufe zu einem einzigen zusammengeführt werden, so wie in Mergesort. Der Stack wird benutzt um all dies nachzuverfolgen. Zum Zusammenführen wird der kleinere der beiden Läufe in einen temporären Speicher verschoben, der hier unten links gezeigt ist. Abhänging von der Position des nun freien Platzes im Array, wird entweder ‘tief’ or ‘hoch’ zusammengeführt. Mit genug Geduld kann man beides auf diesem Panel beobachten.


Bereit zum SortierenLauf findenLauf umkehrenInsertionsort am LaufMergen hochMergen tiefSortierung abgeschlossen 
 
slowerplaypausefaster

Einen besonderen Array sortieren

Dieses Panel zeigt dieselbe Timsort-Anwendung wie auf dem vorherigen, aber mit einem größeren Array von 128 Werten, und bei höherer Geschwindigkeit. Der minrun Parameter wurde zur Verdeutlichung auf 8 gesetzt. Hier sehen wir Eingabedaten die die Komplexität besser veranschaulichen, die entsteht wenn vorhandenen Läufe gemergt werden. Der Gebrauch des Merge Stack stellt sicher, dass Läufe von ähnlicher Größe bevorzugt zusammengeführt werden, bevor sie mit anderen, größeren Läufen zusammenkommen. Dies führt zu besserer Performanz.

Warum also ist Timsort schnell? Zuerst, weil sehr kleine Eingabearrays einfach mit Insertionsort behandelt werden, was für solche auch effizient ist. Zweitens werden eben existierende Läufe genutzt, bis hin zum Fall bei dem das Array bereits sortiert ist und keine Veränderung erforderlich ist. Dies summiert sich bei vielen Fällen schnell auf. Zuletzt ist Mergesort schnell auf großen Arrays, und für große zufällige Eingaben läuft Timsort hierauf hinaus.


Bereit zum SortierenLauf findenLauf umkehrenInsertionsort am LaufMergen hochMergen tiefSortierung abgeschlossen 
 
slowerplaypausefaster

Eine vorsortierte Eingabe

Als letztes Panel zeige ich, wie Timsort teilweise vorsortierte Eingaben sortiert. Das sortierte Array oben hat eine kleine Reihe von Zufallszahlen am Ende angefügt, und muss erneut sortiert werden. Ein Insertionsort könnte dies leicht handhaben, aber das allgemeinere Timsort erkennt die Situation indem es den großen Lauf identifiziert und handhabt die Eingabe ziemlich effizient.

Zum Schluss möchte ich noch darauf eingehen, wie die animierte Implementierung hier vom Python-Original abweicht. Wir kennen schon den minrun Parameter, der künstlich verringert wurde. Weiter ist das Insertionsort im Originalquelltext ein sogenanntes ‘binäres’ Insertionsort, hier wurde ein einfacheres auf Vertauschungsbasis (engl. swaps) verwendet. Als nächstes hat das Original einen sogenannten (engl.) ‘galloping mode’ beim Mergen, was hier gar nicht gezeigt wurde. Galloping wird verwendet, wenn das nächste Element eines Laufes erst drankommt wenn viele andere Elemente des anderen Laufes kopiert worden sind. Somit kann man die Geschwindigkeit weiter verbessern.


Wer der Programmiersprache C mächtig ist, kann sich die Originalfassung für Python hier ansehen (ab Zeile 2162).

Quellen (englischsprachig)