smoothsort

Smoothsort est un algorithme de tri par comparaison inventé en 1981 par Edsger Dijkstra. C'est un tri de complexité en , tout comme le tri par tas dont il est inspiré, et le tri rapide dans la plupart des cas. Mais si les données sont déjà presque triées, il est de complexité en . Ce tri est alors plus rapide que le tri rapide. La transition entre les temps d'exécution entre les listes déjà triées et les listes mélangées ou à l'envers est progressive d'où le nom smoothsort, smooth signifiant doux, lisse. C'est un tri sur place, c'est-à-dire qu'il n'y a pas de zone mémoire allouée supplémentaire pour stocker les éléments. Si l'algorithme smoothsort est plus rapide que le tri par tas pour des listes peu mélangées, il est légèrement plus lent que le tri par tas pour des listes qui sont plutôt dans le sens décroissant au départ. En effet, les données de départ sont alors plus proche de la structure de tas.