Timsort

Complexité en temps
Découvreur ou inventeur	Tim Peters (en)
Date de découverte	2002
Problèmes liés	Algorithme de tri, tri stable (en), tri par comparaison, hybrid algorithm (en), adaptive sort (en)
Structure des données	Tableau
Basé sur	Tri fusion, Tri par insertion
Pire cas
Moyenne
Meilleur cas
Pire cas

Timsort est un algorithme de tri hybride dérivé du tri fusion et du tri par insertion, stable et conçu pour fonctionner de manière efficace sur des données réelles. Il a été mis au point par Tim Peters en 2002 pour le langage de programmation Python.

L'algorithme procède en cherchant des monotonies, c'est-à-dire des parties de l'entrée déjà correctement ordonnées, et peut de cette manière trier efficacement l'ensemble des données en procédant par fusions successives. Pour des entrées de petites tailles, il revient à effectuer un tri fusion.

Timsort est l'algorithme standard de tri utilisé par Python depuis la version 2.3. Il est également utilisé pour trier des données de types non-primitifs en Java 7^[4], ainsi que par Android^[5] et GNU Octave^[6]. Une variante de l'algorithme, Adaptive Shivers Sort, a été proposée par Vincent Jugé^[7]^,^[8]

Principe de fonctionnement

Timsort a été conçu pour tenir compte de l'ordre initial des éléments à trier ; il est en effet possible que ceux-ci soient en pratique déjà partiellement ordonnés.

L'algorithme procède en parcourant le tableau à la recherche de monotonies, c'est-à-dire dans ce cas de suites d'au moins deux éléments consécutifs croissantes ou strictement décroissantes − les monotonies décroissantes sont simplement renversées, le caractère strict est donc indispensable pour garantir la stabilité de l'algorithme.

Pour des raisons de performance, une taille minimum $M$ est fixée pour la longueur des monotonies recherchées : si la monotonie en cours de construction a en pratique une taille inférieure à $M$ , c'est-à-dire si la suite des $M$ éléments présents à cet endroit du tableau n'est pas monotone, une monotonie est artificiellement construite en effectuant un tri par insertion stable sur les $M$ éléments consécutifs présents à l'endroit en question du tableau.

Une pile est utilisée pour mémoriser les monotonies (adresse mémoire et longueur) déjà identifiées. L'algorithme parcourt le tableau en même temps que les monotonies mémorisées dans la pile sont fusionnées deux à deux. Il n'est pas optimal de fusionner une monotonie dès qu'elle est trouvée avec la précédente, car il peut être plus intéressant de prendre en considération les tailles des monotonies suivantes. Toutefois, attendre d'avoir ajouté toutes les monotonies à la pile avant de commencer à les fusionner réduirait également les performances, car fusionner les monotonies le plus rapidement possible permet de tirer profit de la persistance des données dans les couches hautes de la hiérarchie mémoire ; de plus, il est coûteux en espace de mémoriser toutes les monotonies. Dans tous les cas, seules deux monotonies consécutives dans la pile peuvent être fusionnées afin de garantir la stabilité de l'algorithme.

Fusions de monotonies

En pratique, l'algorithme procède aux fusions qui permettent de garantir les propriétés suivantes sur les tailles $N_{1}$ , $N_{2}$ et $N_{3}$ des trois monotonies du dessus de la pile :

$N_{1}>N_{2}+N_{3}$
$N_{2}>N_{3}$

Par exemple, si la propriété (1.) n'est pas satisfaite, la seconde monotonie de la pile va être fusionnée avec la plus petite des première et troisième monotonies, et d'autres fusions peuvent être effectuées par la suite tant que les propriétés ne sont pas vérifiées. L'idée est d'essayer de favoriser les fusions entre monotonies de tailles similaires.

La fusion est effectuée au moyen d'un tableau temporaire, dont la taille est celle de la plus petite des deux monotonies à fusionner.

Choix de la taille minimale des monotonies

Si le nombre $N$ d'éléments à trier est inférieur à 64, la taille minimale $M$ des monotonies est fixée à $N$ et cela revient à effectuer un tri par insertion sur l'ensemble des données. Si ce n'est pas le cas, les valeurs utilisées sont typiquement 16, 32, 64 ou 128. Le choix d'une puissance de 2 est important pour la phase de fusion.

Complexité

Timsort a une complexité en temps dans le pire des cas en $O(N\ln(N))$ . Dans le meilleur cas, qui survient par exemple si la liste est déjà triée, la complexité est linéaire.

La complexité en espace dans le pire des cas est également linéaire en la taille de l'entrée.

Bug concernant le maintien des invariants

Des chercheurs ont montré en utilisant des méthodes formelles, et plus précisément l'outil KeY^[9] que la formulation initiale de l'algorithme ne garantissait pas toujours le maintien des invariants^[10]. Le bug n'a pas été jugé critique car il ne concernait que des entrées de tailles bien supérieures à ce que l'on peut traiter en pratique, mais a toutefois été corrigé rapidement^[11].

Annexes

Notes

↑ Tim Peters (d), « http://mail.python.org/pipermail/python-dev/2002-July/026837.html », 24 février 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). »
↑ « http://drops.dagstuhl.de/opus/volltexte/2018/9467/ » : « TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. »
↑ (en) Badrish Chandramouli et Jonathan Goldstein, « Patience is a virtue: revisiting merge and sort on modern processors », SIGMOD conference,‎ 1^er juin 2014, p. 731-742 (DOI 10.1145/2588555.2593662).
↑ (en) « [#JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort » (consulté le 30 novembre 2015)
↑ (en) Android Gingerbread Documentation, « Class: java.util.TimSort<T> », sur Documentation Android (consulté le 30 novembre 2015)
↑ (en) « liboctave/util/oct-sort.cc », sur Dépôt Mercurial d'Octave (consulté le 30 novembre 2015)
↑ Jugé 2020.
↑ « Vincent Jugé améliore l’algorithme au cœur de Python, Java et Android » sur CNRS Actualités INS2I.
↑ (en) Projet KeY (consulté le 7 décembre 2015)
↑ (en) « Proving that Android’s, Java’s and Python’s sorting algorithm is broken (and showing how to fix it) »
↑ (en) « Python Issue Tracker - Issue 23515: Bad logic in timsort's merge_collapse »

Bibliographie

Nicolas Auger, Cyril Nicaud et Carine Pivoteau, Merge Strategies: from Merge Sort to TimSort [« Stratégies de fusion : du tri-fusion à Timsort »], 2015 (lire en ligne)
Nicolas Auger, Vincent Jugé, Cyril Nicaud et Carine Pivoteau, « On the Worst-Case Complexity of TimSort », dans 26th Annual European Symposium on Algorithms (ESA), Helsinki, Leibniz-Zentrum fuer Informatik, 2018 (DOI 10.4230/LIPIcs.ESA.2018.4, arXiv 1805.08612, lire en ligne), p. 4:1-4:13.
J. Ian Munro et Sebastian Wild, « Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs », dans 26th Annual European Symposium on Algorithms (ESA), Helsinki, Leibniz-Zentrum fuer Informatik, 2018 (DOI 10.4230/LIPIcs.ESA.2018.63, lire en ligne), p. 63:1-63:16.
Vincent Jugé, « Adaptive Shivers Sort: An Alternative Sorting Algorithm », dans 31th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM-ACM, 2020 (DOI 10.1137/1.9781611975994.101, arXiv 1805.08612, lire en ligne), p. 1639-1654.
Sam Buss et Alexander Knop, « Strategies for Stable Merge Sorting », dans 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM-ACM, 2019 (DOI 10.1137/1.9781611975482.78, arXiv 1801.04641v4), p. 1272-1290.

Liens externes

Théorie

(en) « Explications originales de l'auteur, Tim Peters » (consulté le 1^er décembre 2015)

Implémentations

(en) « listobject.c » (consulté le 1^er décembre 2015) − Implémentation en C pour CPython.
(en) « TimSort.java » (consulté le 1^er décembre 2015) − Implémentation Java (langage)
(en) « oct-sort.cc » (consulté le 1^er décembre 2015) − Implémentation C++ pour GNU Octave

[wikidata-e49864ca6eccdb9786cd6469750ece5cb8a7ca27-1] Tim Peters (d), « http://mail.python.org/pipermail/python-dev/2002-July/026837.html », 24 février 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). »

[wikidata-c5a250f1e6c7bc20377926e554ea8864c243aa25-2] « http://drops.dagstuhl.de/opus/volltexte/2018/9467/ » : « TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint. »

[wikidata-5946c04a3d0875fb4ec1c9ddc9c7079b6d860f9cQ93858163-3] (en) Badrish Chandramouli et Jonathan Goldstein, « Patience is a virtue: revisiting merge and sort on modern processors », SIGMOD conference,‎ 1^er juin 2014, p. 731-742 (DOI 10.1145/2588555.2593662).

[java7-4] (en) « [#JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort » (consulté le 30 novembre 2015)

[android-5] (en) Android Gingerbread Documentation, « Class: java.util.TimSort<T> », sur Documentation Android (consulté le 30 novembre 2015)

[octave-6] (en) « liboctave/util/oct-sort.cc », sur Dépôt Mercurial d'Octave (consulté le 30 novembre 2015)

[7] Jugé 2020.

[8] « Vincent Jugé améliore l’algorithme au cœur de Python, Java et Android » sur CNRS Actualités INS2I.

[key-9] (en) Projet KeY (consulté le 7 décembre 2015)

[bug-10] (en) « Proving that Android’s, Java’s and Python’s sorting algorithm is broken (and showing how to fix it) »

[bug-tracker-11] (en) « Python Issue Tracker - Issue 23515: Bad logic in timsort's merge_collapse »

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

Pire cas	$O(n\log(n))$ ^[1]^,^[2]
Moyenne	$O(n\log(n))$
Meilleur cas	$O(n)$ ^[3]