LinkedIn

Trier une liste chaînée : le tri fusion expliqué

Parmi les algorithmes de tri applicables à une liste chaînée, le tri fusion (merge sort) est le plus adapté. La raison est structurelle : il ne nécessite que des déplacements de pointeurs, alors qu'un algorithme comme le tri rapide perd son avantage sur liste chaînée, faute d'accès direct par index.

Le principe « diviser pour régner »

1. Diviser

Si la liste contient zéro ou un nœud, elle est déjà triée : c'est le cas de base. Sinon, on la coupe en deux moitiés à peu près égales. Sur liste chaînée, la technique classique consiste à utiliser deux pointeurs avançant à des vitesses différentes — un pas à pas, l'autre deux par deux. Quand le pointeur rapide atteint la fin, le lent se trouve approximativement au milieu.

2. Conquérir

On applique récursivement le tri fusion à chacune des deux sous-listes, jusqu'à atteindre les cas de base.

3. Fusionner

C'est le cœur de l'algorithme. On parcourt simultanément les deux sous-listes triées à l'aide de deux pointeurs :

  • on compare les valeurs des nœuds pointés ;
  • on raccroche le plus petit à la liste de sortie ;
  • on avance le pointeur correspondant d'un nœud ;
  • on répète jusqu'à épuisement de l'une des deux listes ;
  • on raccorde alors simplement le reste de l'autre liste, déjà trié.

4. Retourner le résultat

La liste obtenue après fusion complète est la liste triée, en ordre croissant (ou décroissant si le comparateur est inversé).

Complexité

Le tri fusion s'exécute en O(n log n) dans tous les cas — meilleur, le pire et moyen — avec un espace auxiliaire O(1) si l'on réutilise les nœuds existants par simple réaffectation de pointeurs. Cette régularité de performance, indépendante de l'ordre initial des données, est un atout par rapport au tri rapide, qui se dégrade en O(n²) sur des données déjà partiellement ordonnées.

Un détail de mise en œuvre

La fusion s'écrit de préférence de façon itérative plutôt que récursive : sur une liste très longue, une fusion récursive ajoute une profondeur de pile qui peut poser problème. En revanche, la phase de division reste naturellement récursive, avec une profondeur en log n, tout à fait acceptable.

Article précédent:
Article suivant:
Articles recommandés