Caractère stable

Un algorithme est dit stable s'il garde l'ordre relatif des quantités égales pour la relation d'ordre.

Exemple, si on considère la suite d’éléments suivante :

(4, 1)  (3, 1)  (3, 7)  (5, 6)

que l'on trie par rapport à leur première coordonnée (la clé), deux cas sont possibles, quand l’ordre relatif est respecté et quand il ne l'est pas :

(3, 1)  (3, 7)  (4, 1)  (5, 6)   (ordre relatif maintenu)

(3, 7)  (3, 1)  (4, 1)  (5, 6)   (ordre relatif changé)

Lorsque deux éléments sont égaux pour la relation d'ordre (c’est-à-dire qu'ils ont la même clé), l'algorithme de tri conserve l'ordre dans lequel ces deux éléments se trouvaient avant son exécution. Les algorithmes de tri instables peuvent être retravaillés spécifiquement afin de les rendre stable, cependant cela peut être aux dépens de la rapidité et/ou peut nécessiter un espace mémoire supplémentaire.