Le tri fusion

Fusionner deux entrées déjà triées

Prenons [2,7] et [1,5,8]. On compare deux et un : un est ajouté au résultat. Puis deux et cinq : deux est ajouté. Puis sept et cinq : cinq est ajouté. Puis sept et huit : sept est ajouté. La première liste est épuisée ; on ajoute le reste, huit. Le résultat est [1,2,5,7,8].

À chaque choix, la plus petite valeur encore disponible se trouve en tête de l’une des deux listes, puisqu’elles sont triées. Le prérequis est essentiel. La fusion ne peut pas compenser une entrée non triée en choisissant seulement parmi les deux positions courantes.

def fusion(gauche, droite):
    i, j = 0, 0
    resultat = []
    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
    resultat.extend(gauche[i:])
    resultat.extend(droite[j:])
    return resultat

Diviser jusqu’aux bases

Une liste vide ou singleton est déjà triée. Sinon, on la coupe en deux parties aussi proches que possible en taille, puis on trie récursivement chaque partie. Une fois ces résultats obtenus, on les fusionne. L’appel parent attend donc les deux réponses avant sa combinaison.

def tri_fusion(valeurs):
    if len(valeurs) <= 1:
        return valeurs.copy()
    milieu = len(valeurs) // 2
    gauche = tri_fusion(valeurs[:milieu])
    droite = tri_fusion(valeurs[milieu:])
    return fusion(gauche, droite)

La fonction fusion est le composant décrit dans cette page. Cette version crée de nouvelles listes et conserve la liste d’entrée. Une implémentation différente pourrait choisir d’autres interfaces, à condition de les annoncer.

Justifier la correction et les doublons

Pendant une fusion, le résultat contient dans l’ordre les plus petites valeurs déjà consommées. Les indices indiquent exactement ce qu’il reste dans chaque entrée. Choisir la plus petite tête conserve cette propriété. Lorsqu’une entrée est vide, le reste de l’autre peut être ajouté puisqu’il est trié et supérieur ou égal au dernier élément choisi.

Les doublons doivent être conservés. Pour une fusion stable, on choisit l’élément de gauche en cas d’égalité : l’ordre relatif d’éléments égaux venant de l’entrée initiale est alors préservé. La stabilité est une propriété supplémentaire utile, distincte du simple ordre croissant des valeurs.

Une liste triée ne suffit pas à certifier un tri correct : elle doit aussi contenir exactement les mêmes occurrences que l’entrée. Pour [4,4,1], [1,4] respecte l’ordre mais perd une donnée. Comparez les longueurs et les multiplicités, puis seulement l’ordre et, si nécessaire, la stabilité.

Compter le travail par niveaux

Fusionner deux listes de longueur totale n demande un travail linéaire : chaque élément est ajouté une fois. Le découpage équilibré produit environ log₂ n niveaux. À un même niveau, les différentes fusions manipulent au total une quantité proportionnelle à n. Le coût global est donc de l’ordre de n log n, y compris dans le pire cas de cette organisation.

La version présentée utilise des listes supplémentaires. Une implémentation standard de tri fusion peut travailler avec une mémoire auxiliaire linéaire, à laquelle s’ajoute une pile logarithmique. Les détails des copies influencent les constantes ; annoncer un tri en place pour ce code serait incorrect.

Exemple suivi : trier une longueur impaire

Pour [7,2,5,1,4], la coupure au milieu entier donne [7,2] et [5,1,4]. Le premier côté devient [2,7]. Le second se coupe en [5] et [1,4], puis devient [1,4,5]. La fusion finale compare 2 et 1, 2 et 4, 7 et 4, 7 et 5 ; elle produit [1,2,4,5] puis ajoute le reste [7]. Le résultat contient cinq valeurs, comme l’entrée.

Une taille impaire ne demande pas une règle spéciale de fusion : les moitiés peuvent différer d’une unité. Ce sont les bornes de division et les cas de base qui doivent rester corrects. Le code emploie des tranches Python pour écrire les parties ; lire valeurs[:milieu] comme la partie avant milieu et valeurs[milieu:] comme celle qui commence à milieu suffit ici. Ces copies ont un coût et font partie de cette implémentation particulière.

Exemple suivi : voir la stabilité avec des étiquettes

Imaginons les données (4,A), (2,B), (4,C), (2,D), à trier seulement selon leur nombre. Une sortie stable conserve B avant D parmi les deux valeurs 2, et A avant C parmi les deux valeurs 4. En fusionnant deux parties, choisir l’élément gauche lorsque les clés sont égales préserve leur ordre initial, puisque la partie gauche venait avant la droite dans l’entrée.

Avec des nombres seuls, les deux occurrences de 4 sont visuellement indiscernables ; leurs étiquettes rendent la propriété testable. La stabilité n’est pas indispensable à chaque usage, mais elle importe lorsqu’un premier classement doit être conservé entre des éléments ex æquo. Les comparaisons comptées dans l’atelier portent sur les valeurs pendant les fusions. Les copies des restes représentent aussi du travail, même lorsqu’elles ne demandent plus de comparaison avec une autre tête.

De la compréhension à l’autonomie

À vous de résoudre

Cherchez d’abord par vous-même. Vérifiez les résultats demandés, utilisez les indices si nécessaire, puis comparez votre méthode à la correction.

Les erreurs qui méritent un détour

Oublier le reste d’une liste après épuisement de l’autre.

Tous les éléments doivent apparaître dans le résultat.

Confondre concaténation et fusion.

La concaténation ne réordonne pas la frontière des deux listes.

Cette notion au bac

Retrouvez ces idées dans un sujet complet, avec des indices, une correction expliquée et des ateliers.

• Bac 2025 · Amérique du Nord · Jour 1 : Organiser les colis et comprendre les limites du glouton

Le prochain pas

• Coûts en temps et en mémoire

Retrouver le catalogue de Terminale

Ce chapitre s’appuie sur le programme officiel de Terminale (PDF, nouvel onglet). Les explications et exercices sont proposés pour l’apprentissage.