Le Tri Fusion
Le tri fusion (ou merge sort) est un algorithme de tri basé sur le paradigme "Diviser pour régner" (Divide and Conquer). Il consiste à diviser récursivement le tableau en deux moitiés jusqu'à obtenir des tableaux d'un seul élément, puis à les fusionner de manière ordonnée.
1 Animation JavaScript
Légende : ■ Comparaison | ■ Fusionné
2 L'Algorithme
L'algorithme se compose de deux parties : la division récursive et la fusion de deux listes triées.
3 Terminaison et Correction
Terminaison (Preuve que l'algorithme s'arrête)
Le tri fusion est une fonction récursive. Pour prouver sa terminaison, on définit un variant de boucle (ou de récurrence) : la taille de la liste $n$.
- À chaque appel récursif, la liste est divisée en deux sous-listes de tailles $n_1 = \lfloor n/2 \rfloor$ et $n_2 = n - \lfloor n/2 \rfloor$.
- Pour $n > 1$, on a toujours $n_1 < n$ and $n_2 < n$.
- La suite des tailles des listes est une suite d'entiers naturels strictement décroissante qui finit par atteindre le cas de base ($n \le 1$).
Correction (Preuve que l'algorithme est juste)
La correction se démontre par récurrence sur la taille $n$ de la liste :
- Initialisation : Pour $n \le 1$, la liste est déjà triée (cas de base).
- Hérédité : Si on suppose que
tri_fusiontrie correctement les listes de taille $< n$, alorsgetdsont deux listes triées. La fonctionfusiondoit alors maintenir un invariant de boucle.
À chaque étape de la boucle
while, la liste resultat contient les $i+j$ plus petits éléments des deux listes gauche et droite, classés par ordre croissant.
Complexité temporelle
Le tri fusion divise la taille du problème par 2 à chaque étape (profondeur de l'arbre récursif : $\log_2 n$) et effectue une fusion linéaire ($n$ opérations) à chaque niveau.
| Cas | Complexité |
|---|---|
| Pire cas | $O(n \log n)$ |
| Meilleur cas | $O(n \log n)$ |
| Complexité spatiale | $O(n)$ (nécessite des tableaux temporaires) |