← Retour aux activités

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

Cliquez sur "Démarrer" pour visualiser la fusion

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.

FONCTION fusion(gauche, droite) resultat = [] i = 0 j = 0 TANT QUE i < longueur(gauche) ET j < longueur(droite) SI gauche[i] <= droite[j] AJOUTER gauche[i] À resultat, i = i + 1 SINON AJOUTER droite[j] À resultat, j = j + 1 TANT QUE i < longueur(gauche) AJOUTER gauche[i] À resultat, i = i + 1 TANT QUE j < longueur(droite) AJOUTER droite[j] À resultat, j = j + 1 RETOURNER resultat FONCTION tri_fusion(liste) n = longueur(liste) SI n <= 1 RETOURNER liste milieu = n // 2 gauche_temp = [] POUR k de 0 à milieu - 1: AJOUTER liste[k] À gauche_temp droite_temp = [] POUR k de milieu à n - 1: AJOUTER liste[k] À droite_temp g = tri_fusion(gauche_temp) d = tri_fusion(droite_temp) RETOURNER fusion(g, d)
def fusion(gauche, droite): resultat = [] i = 0 j = 0 while i < len(gauche) and j < len(droite): if gauche[i] <= droite[j]: resultat.append(gauche[i]) i += 1 else: resultat.append(droite[j]) j += 1 # On ajoute les éléments restants sans extend while i < len(gauche): resultat.append(gauche[i]) i += 1 while j < len(droite): resultat.append(droite[j]) j += 1 return resultat def tri_fusion(liste): n = len(liste) if n <= 1: return liste milieu = n // 2 # On crée les sous-listes sans slicing gauche_temp = [] for k in range(milieu): gauche_temp.append(liste[k]) droite_temp = [] for k in range(milieu, n): droite_temp.append(liste[k]) g = tri_fusion(gauche_temp) d = tri_fusion(droite_temp) return fusion(g, d)

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$.

Correction (Preuve que l'algorithme est juste)

La correction se démontre par récurrence sur la taille $n$ de la liste :

Invariant de la fonction Fusion :
À 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.

CasComplexité
Pire cas$O(n \log n)$
Meilleur cas$O(n \log n)$
Complexité spatiale$O(n)$ (nécessite des tableaux temporaires)

4 Exercices d'application

5 Défis de programmation