Motivation

Le tri fusion (Merge Sort) divise le problème en sous-problèmes plus petits, résout chacun d'eux et combine les résultats. Cette étape de combinaison, la fusion de deux listes déjà triées, est le cœur de l'algorithme.

Pourquoi apprendre le tri fusion ?

• Rapide et prévisible : il s'exécute en un temps O(n log n) dans le meilleur des cas, en moyenne et dans le pire des cas.
• Stable : les éléments égaux conservent leur ordre relatif d'origine.
• Idéal pour les grandes quantités de données : il fonctionne bien lorsque les données ne tiennent pas en mémoire (tri externe) et pour les listes chaînées.
• Diviser pour régner : il enseigne un modèle utilisé dans de nombreux algorithmes avancés.