Tri fusion
Couper la liste en deux, trier chaque moitié, fusionner le tout — O(n log n) dans tous les cas, sans exception.
Décrit par John von Neumann en 1945, ce qui en fait l'un des plus vieux algorithmes encore utilisés en production. L'étape de fusion parcourt deux listes déjà triées et prélève à chaque fois le plus petit des deux éléments de tête, ce qui est linéaire ; la récursion descend sur log n niveaux ; le produit des deux donne la complexité garantie.
Deux propriétés le rendent difficile à remplacer. Il est stable — les éléments égaux conservent leur ordre relatif, ce qu'exige un tri sur plusieurs champs successifs. Et il ne lit qu'en séquentiel, ce qui en fait le choix standard pour les données trop volumineuses pour tenir en mémoire : les tris externes sur disque ou bande reposent encore sur le tri fusion aujourd'hui. Le prix à payer est O(n) de mémoire supplémentaire, là où Quicksort se contente de presque rien mais dégénère en temps quadratique dans le pire des cas. Le tri par défaut de Python et de Java utilise Timsort, un hybride qui repose sur le tri fusion.