Nb l'Element est la cle, Execution : Pour le tableau [89, 7, -2, 0, -1, 34, 2, 78, 80, -100], le tri par insertion donnerait le tableau trié suivant : [-100, -2, -1, 0, 2, 7, 34, 78, 80, 89]. Voici le détail des étapes :
Etape 1 : on commence par prendre l'élément à l'indice 1 (ici 7). On le compare à l'élément précédent (ici 89) et on le place avant si besoin. Le tableau est donc inchangé : [89, 7, -2, 0, -1, 34, 2, 78, 80, -100].
Etape 2 : on prend l'élément à l'indice 2 (ici -2). On le compare aux éléments précédents (89 et 7) et on le place avant si besoin. Le tableau devient : [89, 7, -2, 0, -1, 34, 2, 78, 80, -100].
Etape 3 : on prend l'élément à l'indice 3 (ici 0). On le compare aux éléments précédents (-2, 7 et 89) et on le place avant si besoin. Le tableau devient : [89, 7, -2, 0, -1, 34, 2, 78, 80, -100].
Etape 4 : on prend l'élément à l'indice 4 (ici -1). On le compare aux éléments précédents (-2, 0 et 7) et on le place avant si besoin. Le tableau devient : [89, -2, 0, -1, 7, 34, 2, 78, 80, -100].
Etape 5 : on prend l'élément à l'indice 5 (ici 34). On le compare aux éléments précédents (-2, -1, 0, 7 et 89) et on le place après 89. Le tableau devient : [-2, 0, -1, 7, 34, 89, 2, 78, 80, -100].
Etape 6 : on prend l'élément à l'indice 6 (ici 2). On le compare aux éléments précédents du tableau, en commençant par l'élément à l'indice 5 (ici 34). Comme 2 est plus petit que 34, on décale l'élément 34 d'une position vers la droite pour libérer la place à l'indice 5, et on insère l'élément 2 à l'indice 5 : [89, 7, -2, 0, -1, 34, 34, 78, 80, -100] devient [89, 7, -2, 0, -1, 2, 34, 78, 80, -100].
Etape 7 : on prend l'élément à l'indice 7 (ici 78). On le compare aux éléments précédents du tableau, en commençant par l'élément à l'indice 6 (ici 34). Comme 78 est plus grand que 34, on insère directement l'élément 78 à l'indice 7 : [89, 7, -2, 0, -1, 2, 34, 34, 80, -100] devient [89, 7, -2, 0, -1, 2, 34, 78, 80, -100].
Etape 8 : on prend l'élément à l'indice 8 (ici 80). On le compare aux éléments précédents du tableau, en commençant par l'élément à l'indice 7 (ici 78). Comme 80 est plus grand que 78, on insère directement l'élément 80 à l'indice 8 : [89, 7, -2, 0, -1, 2, 34, 78, 78, -100] devient [89, 7, -2, 0, -1, 2, 34, 78, 80, -100].
Etape 9 : on prend l'élément à l'indice 9 (ici -100). On le compare aux éléments précédents du tableau, en commençant par l'élément à l'indice 8 (ici 80). Comme -100 est plus petit que 80, on décale l'élément 80 d'une position vers la droite pour libérer la place à l'indice 8, et on insère l'élément -100 à l'indice 8 : [89, 7, -2, 0, -1, 2, 34, 78, 80, 80] devient [89, 7, -2, 0, -1, 2, 34, 78, -100, 80].
Le tableau est maintenant trié par ordre croissant : [-100, -2, -1, 0, 2, 7, 34, 78, 80, 89].