Insertion dichotomique

Pour rester stable, $T[k]$ doit être inséré après les valeurs qui lui sont égales : on cherche le premier indice $g$ tel que $T[g:k]>x$, avec l'invariant de dernierIndice.

nom : T
valeurs : _ _ _ _ _ x _ _
colorier : 5
pointeurs : g=2 d=4 k=5
zone : 0..1 au plus x
zone : 2..3 inconnu
zone : 4..4 > x
legende : T[0:k] est trié : I(g,d) dit T[0:g] ≤ x < T[d:k]

static void triInsertionDicho(int[] T) { int n = T.length;
    for (int k = 1; k < n; k++) {
        int x = T[k], g = 0, d = k;
        // I(g,d) : T[0:g] <= x < T[d:k]
        while (g < d) {
            int m = g + (d - g) / 2;
            if (T[m] <= x) g = m + 1; else d = m;
        }
        for (int i = k; i > g; i--) T[i] = T[i - 1]; // décalage de T[g:k]
        T[g] = x;
    }
}

L'insertion de $T[k]$ demande au plus $\lceil {\log }_2(k+1)\rceil$ comparaisons, soit au total environ ${\log }_2(n!)\approx n{\log }_{2}n$. Mais les décalages sont les mêmes que dans le tri par insertion : $k-g$ pour l'insertion de $T[k]$, soit en moyenne $n^2/4$ et au pire $n(n-1)/2$.

14.3 n=1000 : trie=true, 8566 comparaisons (n log2 n = 9966), 250949 deplacements (n^2/4 = 250000)
14.3 n=4000 : trie=true, 42370 comparaisons (n log2 n = 47863), 4019225 deplacements (n^2/4 = 4000000)

La complexité reste $\Theta (n^2)$ à cause des décalages. Le gain est réel quand une comparaison coûte cher (comparer deux longues chaînes, par exemple) et qu'un décalage est bon marché.