Tri par fusion

Le tri par fusion (en Anglais : merge sort) est un algorithme de tri de complexité $O(n \texttt{log} n)$ particulièrement bien adapté aux listes. Sa performance est plus sûre que celle du tri rapide, car il n'y a pas de cas pathologiques.

Le principe est simple. Pour trier une liste, on la coupe d'abord en deux parties de tailles égales. Ces deux parties sont triées récursivement, puis fusionnées. La fusion construit une liste triée à partir des deux listes triées en temps linéaire en choisissant à chaque étape le plus petit élément (selon l'ordre choisi) des deux têtes de liste.

Le tri par fusion est particulièrement simple à implémenter en Common Lisp, car il existe déjà une fonction merge qui réalise exactement la fusion, deuxième étape du tri par fusion. La première étape n'est pas très compliquée non plus.

Voici le code :

triparfusion.lisp