Pourquoi le tri fusion a une complexité en O(n log n) ?

Parce que l'algorithme divise la liste en deux à chaque niveau de récursion (ce qui donne log₂(n) niveaux), et à chaque niveau, il doit fusionner l'ensemble des éléments, ce qui représente une opération de coût linéaire O(n). En multipliant le nombre de niveaux par le travail à chaque niveau, on obtient O(n * log n) = O(n log n).

Le tri fusion est-il plus rapide que le tri rapide (Quicksort) ?

Pas toujours. En pratique, Quicksort a souvent de meilleures performances moyennes car ses constantes multiplicatives sont plus petites et il trie "en place" (moins d'allocations mémoire). Cependant, le tri fusion a l'avantage d'avoir une complexité garantie O(n log n) même dans le pire des cas, alors que Quicksort peut dégénérer en O(n²). Le tri fusion est aussi stable, contrairement à une implémentation naïve de Quicksort.

Comment trier une liste de chaînes de caractères avec le tri fusion ?

L'implémentation Python donnée fonctionne déjà pour les chaînes de caractères ! L'opérateur de comparaison <= est défini pour les strings (ordre lexicographique). Il suffit d'appeler `tri_fusion(['pomme', 'banane', 'abricot'])`. L'algorithme est générique et fonctionne pour tout type de données sur lequel on peut définir une relation d'ordre (nombres, chaînes, tuples, etc.).

Peut-on implémenter le tri fusion de manière itérative (sans récursivité) ?

Oui, c'est possible et cela évite les limites de la récursion. L'approche itérative, dite "bottom-up", consiste à considérer la liste comme une succession de sous-listes de taille 1 (déjà triées), puis à les fusionner deux par deux pour créer des sous-listes triées de taille 2, puis 4, etc., jusqu'à obtenir la liste complètement triée. L'algorithme reste en O(n log n) mais est un peu plus complexe à écrire.

Le tri fusion (Merge Sort) expliqué et codé en Python

Q: Peut-on implémenter le tri fusion de manière itérative (sans récursivité) ?

Oui, c'est possible et cela évite les limites de la récursion. L'approche itérative, dite "bottom-up", consiste à considérer la liste comme une succession de sous-listes de taille 1 (déjà triées), puis à les fusionner deux par deux pour créer des sous-listes triées de taille 2, puis 4, etc., jusqu'à obtenir la liste complètement triée. L'algorithme reste en O(n log n) mais est un peu plus complexe à écrire.

Qu'est-ce que le tri fusion (Merge Sort) ?

Le tri fusion, ou Merge Sort, est un algorithme de tri de type « diviser pour régner » (divide and conquer). C'est l'un des algorithmes de tri les plus importants à maîtriser en NSI, car il combine efficacité et élégance conceptuelle. Contrairement à des algorithmes plus simples comme le tri par insertion ou le tri à bulles, qui ont une complexité quadratique O(n²), le tri fusion atteint une complexité bien meilleure de O(n log n). Cela signifie qu'il reste performant même avec de très grands ensembles de données, ce qui en fait un choix privilégié dans de nombreuses applications réelles.

Le principe de « Diviser pour Régner »

Le tri fusion repose entièrement sur une stratégie algorithmique fondamentale : diviser pour régner. Cette stratégie se décompose en trois étapes récursives :

Diviser : On découpe le problème principal (trier une grande liste) en sous-problèmes plus petits et identiques (trier des sous-listes).
Régner : On résout les sous-problèmes de manière récursive. Si un sous-problème est suffisamment petit (une liste de 0 ou 1 élément), il est déjà trié !
Combiner : On fusionne (merge) les solutions des sous-problèmes pour former la solution du problème initial.

Dans le cas du tri fusion, l'étape de combinaison, où l'on fusionne deux listes déjà triées en une seule liste triée, est le cœur de l'algorithme et ce qui lui donne son nom.

Fonctionnement détaillé de l'algorithme

Voyons comment l'algorithme procède étape par étape pour trier une liste comme [38, 27, 43, 3, 9, 82, 10].

Étape 1 : La division récursive

L'algorithme commence par diviser la liste en deux moitiés de taille à peu près égale. Il continue ensuite à diviser chaque sous-liste en deux, et ainsi de suite, de manière récursive, jusqu'à ce que chaque sous-liste ne contienne plus qu'un seul élément (ou zéro). Une liste d'un élément est, par définition, déjà triée !

Étape 2 : La fusion (Merge)

C'est l'étape clé. Une fois la division terminée, on commence à remonter la récursion en fusionnant les petites listes triées. Pour fusionner deux listes triées A et B en une liste C triée :

On compare les premiers éléments de A et de B.
On place le plus petit des deux en tête de la liste C.
On retire cet élément de sa liste d'origine.
On répète le processus jusqu'à ce qu'une des deux listes soit vide.
On ajoute enfin tous les éléments restants de l'autre liste à la fin de C.

Cette opération de fusion est linéaire, sa complexité est O(n) pour fusionner deux listes de taille totale n.

Implémentation en Python

Voici une implémentation classique et pédagogique du tri fusion en Python. Nous allons créer deux fonctions : une pour la fusion (fusionner) et une pour le tri principal (tri_fusion).

La fonction de fusion

def fusionner(gauche, droite):
    """Fusionne deux listes triées (gauche et droite) en une liste triée."""
    resultat = []
    i = j = 0  # Index pour parcourir les listes 'gauche' et 'droite'

    # Comparer et ajouter le plus petit élément
    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

    # Ajouter les éléments restants (une des deux listes est vide)
    resultat.extend(gauche[i:])
    resultat.extend(droite[j:])

    return resultat

La fonction de tri récursif

def tri_fusion(liste):
    """Implémente l'algorithme du tri fusion de manière récursive."""
    # Cas de base : une liste de 0 ou 1 élément est déjà triée
    if len(liste) <= 1:
        return liste

    # Étape DIVISER : on coupe la liste en deux
    milieu = len(liste) // 2
    gauche = liste[:milieu]
    droite = liste[milieu:]

    # Étape RÉGNER : on trie récursivement chaque moitié
    gauche_triee = tri_fusion(gauche)
    droite_triee = tri_fusion(droite)

    # Étape COMBINER : on fusionne les deux moitiés triées
    return fusionner(gauche_triee, droite_triee)

# Exemple d'utilisation
ma_liste = [38, 27, 43, 3, 9, 82, 10]
liste_triee = tri_fusion(ma_liste)
print("Liste triée :", liste_triee)  # Affiche : [3, 9, 10, 27, 38, 43, 82]

Analyse de la complexité

L'analyse de la complexité du tri fusion est un excellent exercice pour comprendre la récursivité.

Complexité en temps : O(n log n) dans tous les cas (pire, moyen, meilleur). C'est sa grande force. La hauteur de l'arbre de récursion est log₂(n) (car on divise par 2 à chaque fois), et à chaque niveau, on fait une opération de fusion de coût O(n). D'où n * log n.
Complexité en espace : O(n). Contrairement à un tri en place comme le tri rapide (qui peut être O(log n) pour la pile d'appels), le tri fusion a besoin de créer de nouvelles listes lors des fusions, ce qui nécessite un espace mémoire supplémentaire proportionnel à la taille des données. C'est son principal inconvénient.

À retenir : Le tri fusion est stable (il préserve l'ordre des éléments égaux) et prédictible (toujours O(n log n)), mais il n'est pas en place.

Avantages, inconvénients et applications

Le tri fusion n'est pas qu'un exercice académique. Il est utilisé dans de nombreux logiciels réels.

Avantages

Complexité garantie O(n log n).
Algorithme stable.
Parallélisable : les sous-tris peuvent être effectués indépendamment sur différents cœurs de processeur.
Très efficace pour trier des données qui ne tiennent pas en mémoire vive (tri externe), comme les gros fichiers.

Inconvénients

Complexité spatiale O(n), nécessite de la mémoire supplémentaire.
La récursivité peut entraîner une surcharge d'appels de fonction pour de très grandes listes (débordement de pile possible, bien que rare en Python avec la limite de récursion par défaut).

Applications concrètes

Le tri fusion est l'algorithme utilisé par la fonction sorted() en Python pour les listes de type list (l'implémentation réelle, Timsort, est un hybride dérivé du tri fusion et du tri par insertion).
Tri de grandes bases de données.
Dans les systèmes de gestion de versions comme Git, pour fusionner des branches.