On appelle inversion d'un tableau un couple d'indices avec et

def inversions(t):
    """Nombre de couples (i, j), i < j, avec t[i] > t[j]. Coût quadratique."""
    n = 0
    for i in range(len(t)):
        for j in range(i + 1, len(t)):
            if t[i] > t[j]:
                n = n + 1
    return n

La démonstration. Le tri par insertion ne fait qu'une seule chose qui modifie l'ordre : décaler d'un cran vers la droite un élément t[j-1] strictement plus grand que la carte x qui vient de sa droite. Ce décalage fait donc passer x devant t[j-1] : il supprime exactement une inversion, celle du couple $(\text{j-1},\text{position de }x)$. Il n'en crée aucune autre — les éléments décalés gardent leur ordre relatif. Comme le tableau final, trié, n'a aucune inversion, le nombre total de décalages vaut le nombre d'inversions du tableau initial.

La vérification. Sur $3000$ tableaux tirés au hasard, avec doublons :

assert decalages == inversions(t)

$3000$ cas passent. Trois exemples lisibles :

L'encadrement des comparaisons. Chaque décalage est précédé d'une comparaison réussie ; et chaque tour de la boucle externe se termine par au plus une comparaison ratée — celle qui arrête la boucle interne. D'où

$$\text{inv}\le \text{comparaisons}\le \text{inv}+(n-1).$$

Vérifié sur $2000$ tableaux : aucune assertion ne se déclenche. Sur [1, 2, 3, 4] : $0\le 3\le 0+3$, borne haute atteinte. Sur [4, 3, 2, 1] : $6\le 6\le 9$, borne basse atteinte.

Ce que ce résultat explique. « Le tri par insertion est rapide sur des données presque triées » n'est plus une impression, c'est un théorème : son coût est proportionnel au désordre, mesuré par le nombre d'inversions. Un tableau à $n$ éléments et $k$ inversions se trie en $k+n$ opérations environ — linéaire si $k$ est petit, quadratique seulement si $k$ approche son maximum $n(n-1)/2$.