Instrumenter le tri par insertion pour compter ses comparaisons, et…

def tri_insertion_compte(t):
    """Comme tri_insertion, mais rend (comparaisons, décalages)."""
    comp = 0
    dec = 0
    for i in range(1, len(t)):
        x = t[i]
        j = i
        while j > 0:
            comp = comp + 1
            if t[j - 1] > x:
                t[j] = t[j - 1]
                j = j - 1
                dec = dec + 1
            else:
                break
        t[j] = x
    return comp, dec

(colonne « aléatoire » : moyenne sur $400$ tirages par taille.)

Les trois rapports, quand $n$ double.

Ce que les mesures confirment, et ce qu'elles ajoutent. Le meilleur cas double quand $n$ double, le pire quadruple : ce sont exactement les deux lois du cours. La colonne « à l'envers » vaut exactement $n(n-1)/2$, ce qui n'est pas une approximation mais une identité — chaque élément traverse toute la partie triée.

L'ajout, c'est la colonne aléatoire : elle quadruple aussi, donc elle est quadratique, mais elle vaut environ la moitié du pire cas ($2559$ contre $4950$). Le tri par insertion sur des données quelconques n'est donc pas « entre le linéaire et le quadratique » : il est quadratique, avec un coefficient deux fois plus petit. Un facteur constant ne change pas la loi — et c'est la première chose que la mesure sur trois tailles permet de trancher.