03 — Le tri par fusion, diviser pour régner

Ce que tu vas apprendre

• La stratégie diviser pour régner appliquée au tri
• Comment fusionner deux moitiés triées en O(n)
• Pourquoi le tri par fusion est en O(n log n) dans tous les cas
• Son coût mémoire et pourquoi il est stable

Prérequis

• 02 — Tri à bulles
• La notation Big-O, en particulier O(n log n)

On quitte les tris quadratiques. Le tri par fusion est le premier de la série à atteindre O(n log n), et il y arrive avec une garantie que peu d'algorithmes offrent : cette complexité tient dans tous les cas, sans pire cas dégradé. C'est aussi l'illustration la plus claire de la stratégie diviser pour régner, qu'on retrouvera dans toute l'algorithmie.

Diviser pour régner

L'idée : un gros problème difficile devient facile si on le découpe en sous-problèmes identiques mais plus petits, qu'on résout, puis dont on combine les solutions. Pour le tri :

1. Diviser : couper le tableau en deux moitiés.
2. Régner : trier chaque moitié, récursivement (chaque moitié se recoupe à son tour, jusqu'à des tableaux d'un seul élément, qui sont triés par définition).
3. Combiner : fusionner les deux moitiés triées en un tableau trié.

Toute la subtilité est dans l'étape de fusion. Le reste n'est que de la récursion.

Fusionner deux moitiés triées

Fusionner, c'est prendre deux tableaux déjà triés et les entrelacer en un seul tableau trié. On avance avec un pointeur sur chaque moitié et on prend à chaque étape le plus petit des deux éléments en tête.

typescriptfunction fusion(gauche: number[], droite: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;
  while (i < gauche.length && j < droite.length) {
    if (gauche[i] <= droite[j]) {
      result.push(gauche[i++]); // <= préserve la stabilité
    } else {
      result.push(droite[j++]);
    }
  }
  // un des deux est épuisé : on ajoute le reste de l'autre
  while (i < gauche.length) result.push(gauche[i++]);
  while (j < droite.length) result.push(droite[j++]);
  return result;
}

Chaque élément des deux moitiés est examiné une seule fois, donc la fusion de n éléments coûte O(n). Le <= (et non <) garantit que, à égalité, l'élément de la moitié gauche passe en premier : c'est ce qui rend le tri stable.

L'algorithme complet

pythondef tri_fusion(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr                      # cas de base : déjà trié
    milieu = len(arr) // 2
    gauche = tri_fusion(arr[:milieu])   # trier la moitié gauche
    droite = tri_fusion(arr[milieu:])   # trier la moitié droite
    return fusion(gauche, droite)       # combiner

def fusion(gauche: list[int], droite: list[int]) -> list[int]:
    result = []
    i = j = 0
    while i < len(gauche) and j < len(droite):
        if gauche[i] <= droite[j]:
            result.append(gauche[i]); i += 1
        else:
            result.append(droite[j]); j += 1
    result.extend(gauche[i:])
    result.extend(droite[j:])
    return result

Pourquoi O(n log n), toujours

La complexité se lit dans la structure récursive. À chaque niveau de découpage, on divise la taille par deux : il faut donc log₂(n) niveaux pour atteindre des tableaux d'un élément. C'est le facteur log n.

À chaque niveau, toutes les fusions réunies traitent l'ensemble des n éléments une fois : c'est le facteur n. On multiplie les deux : n × log n. Et comme le découpage est toujours en deux moitiés égales, peu importe que les données soient triées, aléatoires ou inversées : le tri par fusion fait le même travail. Son meilleur, son moyen et son pire cas sont tous en O(n log n). C'est une garantie forte, que le tri rapide, on le verra, n'offre pas.

Le prix à payer : la mémoire

Le tri par fusion n'est pas en place. La fusion construit un nouveau tableau, ce qui demande O(n) d'espace supplémentaire (en plus de la pile de récursion en O(log n)). C'est son principal défaut face au tri rapide, qui trie en place.

Ce compromis (mémoire contre garantie de complexité et stabilité) explique où on l'utilise. Le tri par fusion est le choix quand la stabilité est requise et qu'on peut se permettre la mémoire, ou quand on trie des données qui ne tiennent pas en RAM (tri externe sur disque, où la fusion s'adapte naturellement aux flux). Il est aussi la base de Timsort, le tri réel de Python et de la JVM, qu'on verra à l'article 07.

L'article suivant présente l'autre grand tri en O(n log n), le plus utilisé de tous malgré un pire cas en O(n²) : le tri rapide.

Sources

• Videau, M., & Eck, D. (2004). Les algorithmes de tri. Interstices. interstices.info/les-algorithmes-de-tri/
• Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Section 2.3 "Designing Algorithms" (merge sort) et Chapitre 4 "Divide-and-Conquer". MIT Press.
• von Neumann, J. (1945). Première description connue du tri par fusion, rapportée par Knuth (1998). TAOCP Vol. 3. Addison-Wesley.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 2.2 "Mergesort". Addison-Wesley.