YAMS, ou « Yet Another Merge Sort », est un algorithme de tri hybride basé sur le bon vieux principe du tri fusion, modifié avec quelques astuces qui, à ma connaissance, n'ont pas encore été incorporées dans un algorithme de tri. C’est plus une évolution qu’une révolution, mais son étude et sa structure méritent de s'y attarder, surtout si vous ne connaissez pas encore la deque.
Je pensais que tout avait déjà été inventé et que la question du tri était réglée depuis les années 60. C'est sans compter l'évolution des besoins, des architectures, et surtout des connaissances qui se croisent et s'émulent pour donner de nouvelles combinaisons inattendues. Revisitons donc ce vieux classique...
1. Théorie
Pourtant, il existe déjà tellement d'algorithmes de tri qu'en inventer un autre ne vaut pas la peine. Après tout, on connaît déjà tout de cette classe d'algorithmes et rien que la page Wikipédia sur le sujet [1] regorge de références toutes plus hétéroclites les unes que les autres. Je ne suis même pas sûr que Donald Knuth arrive un jour à en faire le tour. De plus, on sait pertinemment que l'algorithme de tri par racine (plus communément appelé radix sort) bat tous les autres à plate couture [2]. Ce ne sont au final que de banales permutations, n'est-ce pas, alors à quoi bon essayer de réinventer la...
- Accédez à tous les contenus de Connect en illimité
- Découvrez des listes de lecture et des contenus Premium
- Consultez les nouveaux articles en avant-première