Écrire le tri fusion : couper en deux, trier chaque moitié, fusionner.

def fusionner(a, b):
    """Fusionne deux tableaux TRIÉS en un seul tableau trié."""
    res = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            res.append(a[i]); i = i + 1
        else:
            res.append(b[j]); j = j + 1
    res.extend(a[i:])
    res.extend(b[j:])
    return res

def tri_fusion(t):
    """Trie t. Rend un tableau NEUF."""
    if len(t) <= 1:
        return list(t)
    m = len(t) // 2
    return fusionner(tri_fusion(t[:m]), tri_fusion(t[m:]))

Validation : $2000$ tableaux tirés au hasard — $2000$ cas passent.

La mesure, sur des tableaux aléatoires.

Comment les rapports identifient la loi. Ils valent un peu plus de $2$, et ils décroissent vers $2$ : $2,37$, $2,32$, $2,27$, $2,23$. C'est exactement la signature de $n{\log }_{2}n$ : quand $n$ double, ce produit est multiplié par $2\cdot \frac{{\log }_{2}n+1}{{\log }_{2}n}$, un facteur qui tend vers $2$ par valeurs supérieures. Comparez à la colonne quadratique, dont les rapports valent $4,0$ tout du long, et à un coût linéaire, dont ils vaudraient exactement $2,0$.

Le gain. À $n=1600$ : $15012$ comparaisons contre $1279200$ pour le tri par sélection, soit $85$ fois moins. Et l'écart croît avec $n$ — c'est ce que « meilleure loi » veut dire, par opposition à « meilleur coefficient ».

Le prix. Le tri fusion alloue des tableaux intermédiaires : il n'est pas en place. Et il est récursif, ce que le programme de première écarte explicitement — d'où sa présence ici et non dans le cours. Il se réécrit sans récursivité, mais le code y perd toute sa clarté.