Le tri fusion est un algorithme récursif de tri. Ce tri est basé sur la technique algorithmique diviser pour régner.
L'opération principale de l'algorithme est la fusion, qui consiste à réunir deux listes triées en une seule.
L'algorithme est naturellement décrit récursivement.
- On coupe en deux parties à peu près égales les données à trier
- On trie les données de chaque partie (pour cela, on coupe chaque partie en deux et on trie chacune)
- On fusionne les deux parties
La récursivité s'arrête car on finit par arriver à des listes composées d'un seul élément et le tri est alors trivial.
On commence par générer une liste (on peut paramétrer la taille de la liste).
Ensuite on exécute l'algorithme pas à pas.
