Que se passe-t-il si l'on remplace t j - 1 x par t j - 1 = x

Le tri reste correct. La postcondition « t est croissant et contient les mêmes éléments » est vérifiée dans les deux cas : $2000$ tableaux tirés au hasard dans $\{0,\dots ,5\}$ — donc pleins de doublons — donnent le même résultat que sorted. L'invariant tient encore : x est déposé après tous les éléments strictement plus petits, ce qui suffit à trier.

Le coût, lui, change du tout au tout. Sur un tableau de $200$ éléments tous égaux :

Avec >, la condition est fausse d'emblée à chaque tour — c'est le meilleur cas, $n-1=199$ comparaisons, aucun mouvement. Avec >=, elle est vraie jusqu'au bout : chaque élément traverse toute la partie triée, soit $200\times 199/2=19900$. Le meilleur cas est devenu le pire cas, et le rapport est de cent.

La seconde conséquence : la stabilité est perdue. Trions les couples [(1, 'a'), (1, 'b'), (0, 'c')] sur leur première composante :

Avec >=, 'b' est passé devant 'a' : les ex æquo ont été inversés. Sur une table (chapitre 6), cela ruine le tri en deux temps, qui repose entièrement sur la stabilité.

La leçon. Un caractère de plus laisse le programme correct et détruit deux de ses propriétés — le coût dans le meilleur cas, et la stabilité. Un test ordinaire ne verrait rien : le tableau sort trié. La correction n'est pas la seule chose qu'un programme doit garantir.