Quels tris sont stables ?

• Insertion : stable. Une valeur ne passe devant une autre que si celle-ci est strictement plus grande (test T[i-1] > x) : deux valeurs égales ne se croisent jamais.
• Fusion : stable. En cas d'égalité, le test T[a] <= T[b] prend d'abord la valeur de la moitié gauche, qui était avant dans le tableau.
• Sélection : non stable. L'échange envoie $T[k]$ loin derrière. Avec des couples triés selon la première composante :

14.11 selection : (1,3) (2,2) (2,1)
14.11 insertion : (1,3) (2,1) (2,2)

Au départ $(2,1),(2,2),(1,3)$ : le minimum $(1,3)$ est échangé avec $(2,1)$, qui passe derrière $(2,2)$.

valeurs : (2,1)|(2,2)|(1,3)
colorier : 0 2
fleches : 2->0
fleches-bas : 0->2
legende : le minimum (1,3) prend la case 0 ; (2,1) passe derrière (2,2)

• Rapide : non stable. La segmentation échange des cases éloignées. Sur $[(1,a),(2,b),(1,c)]$ avec pour pivot la dernière case $(1,c)$ : $(1,a)\le (1,c)$ reste en place, puis le pivot est échangé avec $(2,b)$ ; on obtient $(1,a),(1,c),(2,b)$, ce qui est stable ici, mais avec $[(2,a),(2,b),(1,c)]$ on obtient $(1,c),(2,b),(2,a)$ : $a$ et $b$ ont été inversés.
• Tas : non stable. Sur $[(1,a),(1,b)]$ (déjà un tas), la première extraction échange la racine $(1,a)$ avec la dernière case : le résultat est $(1,b),(1,a)$.