Terminale · Numérique et sciences informatiques

Comprendre le tri fusion : diviser, trier, fusionner

Expliquer le fonctionnement du tri fusion récursif, dérouler la fusion de deux listes triées, justifier sa terminaison et sa correction, et établir son coût en O(n log n) sans confondre avec un tri en place.

Aperçu gratuit
Illustration de la fiche « Comprendre le tri fusion : diviser, trier, fusionner »

Les points essentiels

  • Le tri fusion applique le paradigme diviser pour régner : on coupe la liste en deux moitiés, on trie chaque moitié récursivement, puis on fusionne les deux moitiés triées en une seule liste triée.
  • Cas de base : une liste de longueur 0 ou 1 est déjà triée. Ce cas arrête la récursion et sert de point d'appui à la preuve.

Les mots à connaître

Diviser pour régner
Stratégie algorithmique consistant à découper un problème en sous-problèmes de même nature et plus petits, à les résoudre (souvent récursivement), puis à combiner leurs solutions pour obtenir celle du problème initial.
Fusion de deux listes triées
Opération qui construit, à partir de deux listes triées par ordre croissant, une unique liste triée contenant tous leurs éléments, en comparant à chaque étape les deux plus petits éléments non encore utilisés.

Un exemple pour comprendre

Fusionner à la main les listes triées G = [2, 5, 9] et D = [1, 5, 7, 8] en suivant l'algorithme de fusion (en cas d'égalité, on prend l'élément de G). Donner le résultat et le nombre de comparaisons effectuées.

On pose i = 0 (dans G) et j = 0 (dans D). Comparaison 1 : 2 contre 1, on prend 1 (j = 1). Comparaison 2 : 2 contre 5, on prend 2 (i = 1). Comparaison 3 : 5 contre 5, égalité donc on prend le 5 de G (i = 2). Comparaison 4 : 9 contre 5, on prend le 5 de D (j = 2). Comparaison 5 : 9 contre 7, on prend 7 (j = 3). Comparaison 6 : 9 contre 8, on prend 8 (j = 4). D est épuisée : on recopie le reste de G, soit 9. Résultat : [1, 2, 5, 5, 7, 8, 9], de longueur 7 = 3 + 4. Il y a eu 6 comparaisons, ce qui est inférieur à 7 : au plus n - 1 comparaisons pour n éléments, donc la fusion est linéaire.

Première page de l’Essentiel : Comprendre le tri fusion : diviser, trier, fusionner
Ketty