Le tri fusion et les complexités comparées

Le tri fusion applique une stratégie très puissante : « diviser pour régner ». On coupe le tableau en deux moitiés, on trie chaque moitié récursivement (donc de la même façon, en la recoupant encore en deux), puis on fusionne les deux moitiés triées en une seule liste triée. La fusion de deux listes déjà triées est rapide : on compare simplement leurs premiers éléments restants et on prend le plus petit à chaque fois.

Arbre de fusion sur [6, 3, 8, 2] :

niveau 0 (division) :          [6, 3, 8, 2]
                               /            \
niveau 1 (division) :     [6, 3]           [8, 2]
                          /     \           /     \
niveau 2 (base)   :    [6]     [3]       [8]     [2]

remontee (fusion) :
niveau 1 (fusion) :     [3, 6]             [2, 8]
niveau 0 (fusion) :            [2, 3, 6, 8]

À chaque niveau de l'arbre, fusionner toutes les paires coûte au total O(n) comparaisons (chaque élément est regardé une fois). Or il y a environ log2(n) niveaux, puisqu'on divise la taille par deux à chaque étage. Le coût total est donc O(n log n) : bien meilleur que O(n²) quand n devient grand.

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

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

Comparaison des complexités (n = taille du tableau) :

selection : O(n^2)   (toujours, meme si deja trie)
insertion : O(n^2) pire cas, O(n) meilleur cas (presque trie)
bulles    : O(n^2) pire cas, O(n) meilleur cas (avec le drapeau d'arret)
fusion    : O(n log n) toujours (mais utilise de la memoire supplementaire)

Piège classique : croire que le tri fusion est toujours le meilleur choix — il consomme plus de mémoire (les sous-listes temporaires) qu'un tri en place comme le tri à bulles ou l'insertion.