Timsort

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, ainsi que par Android et GNU Octave. Une variante de l'algorithme, Adaptive Shivers Sort, a été proposée par Vincent Jugé 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 est fixée pour la longueur des monotonies recherchées : si la monotonie en cours de construction a en pratique une taille inférieure à , c'est-à-dire si la suite des é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 é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.