Compter les inversions

• On compte, pour chaque valeur, les valeurs plus petites situées à sa droite : $4\to 3$ ($1,3,2$), $7\to 5$, $1\to 0$, $3\to 1$, $8\to 3$, $2\to 0$, $6\to 1$, $5\to 0$. Total : $13$ inversions. Un tableau strictement décroissant a le maximum d'inversions : tous les couples, soit $n(n-1)/2$.
• Les inversions de $T[i:j]$ sont celles de la moitié gauche, celles de la moitié droite, et les couples « à cheval » ($x$ à gauche, $y$ à droite, $x>y$). Ces dernières ne dépendent pas de l'ordre à l'intérieur des moitiés : on peut les compter pendant la fusion des deux moitiés triées. Quand $T[b]$ (à droite) passe devant $T[a]$, c'est que $T[a]>T[b]$, donc toutes les valeurs restantes de $T[a:k]$, qui sont $\ge T[a]$, forment une inversion avec $T[b]$ : il y en a $k-a$.

nom : T
valeurs : 1 3 4 7 2 5 6 8
griser : 0
colorier : 4
fleches : 4->1:+3
pointeurs : a=1 k=4 b=4
zone : 1..3 3 inversions
legende : fusion finale : 1 est déjà copié, 2 passe devant T[a:k] = [3, 4, 7]

static long inversions(int[] T, int i, int j, int[] B) { // trie T[i:j]
    if (j - i <= 1) return 0;
    int k = (i + j) / 2;
    long n = inversions(T, i, k, B) + inversions(T, k, j, B);
    int a = i, b = k, c = i;
    while (a < k && b < j) {
        if (T[a] <= T[b]) B[c++] = T[a++];
        else { n += k - a; B[c++] = T[b++]; } // T[b] passe devant T[a:k]
    }
    while (a < k) B[c++] = T[a++];
    while (b < j) B[c++] = T[b++];
    System.arraycopy(B, i, T, i, j - i);
    return n;
}

13.6 : inversions de [4, 7, 1, 3, 8, 2, 6, 5] = 13 (naif 13)
13.6 : 300 tests aleatoires : true

Le comptage ajoute un temps constant par pas de fusion : la complexité est celle du tri par fusion, $\Theta (n\log n)$, contre $\Theta (n^2)$ pour le comptage naïf des couples. Le test « $T[a]\le T[b]$ » est essentiel : deux valeurs égales ne forment pas une inversion.