Voici les étapes de l'exécution du tri par insertion sur le tableau T = [9,6,1,4,8]. Le tableau est représenté au début et à la fin de chaque itération.
i = 1
9
6
1
4
8
6
9
1
4
8
i = 2
6
9
1
4
8
1
6
9
4
8
i = 3
1
6
9
4
8
1
4
6
9
8
i = 4
1
4
6
9
8
1
4
6
8
9
Combinaison avec d'autres tris
En pratique, les algorithmes de tri en
basés sur la méthode « diviser pour régner » (tri fusion, tri rapide) sont moins efficaces que le tri par insertion sur les petites entrées, en dessous d'une taille critique K (qui dépend de l'implémentation et de la machine utilisée). Dans ce type d'algorithmes, plutôt que de diviser récursivement l'entrée jusqu'à avoir des sous-problèmes élémentaires de taille 1 ou 2, on peut s'arrêter dès que les sous-problèmes ont une taille inférieure à K et les traiter avec le tri par insertion.
Pour le cas particulier du tri rapide, une variante plus efficace existe :
exécuter d'abord le tri rapide en ignorant simplement les sous-problèmes de taille inférieure à K ;
faire un tri par insertion sur le tableau complet à la fin, ce qui est rapide car la liste est déjà presque triée.
Variantes et optimisations
Optimisations pour les tableaux
Plusieurs modifications de l'algorithme permettent de diminuer le temps d'exécution, bien que la complexité reste quadratique.
On peut optimiser ce tri en commençant par un élément au milieu de la liste puis en triant alternativement les éléments après et avant. On peut alors insérer le nouvel élément soit à la fin, soit au début des éléments triés, ce qui divise par deux le nombre moyen d'éléments décalés. Il est possible d'implémenter cette variante de sorte que le tri soit encore stable.
En utilisant une recherche par dichotomie pour trouver l'emplacement où insérer l'élément, on peut ne faire que
comparaisons. Le nombre d'affectations reste en O(n2).
L'insertion d'un élément peut être effectuée par une série d'échanges plutôt que d'affectations. En pratique, cette variante peut être utile dans certains langages de programmation (par exemple C++), où l'échange de structures de données complexes est optimisé, alors que l'affectation provoque l'appel d'un constructeur de copie(en).
Le tri de Shell est une variante du tri par insertion qui améliore sa complexité asymptotique, mais n'est pas stable.
Tri par insertion sur des listes
Le principe du tri par insertion peut être adapté à des listes chaînées. Dans ce cas, le déplacement de chaque élément peut se faire en temps constant (une suppression et un ajout dans la liste). Par contre, le nombre de comparaisons nécessaires pour trouver l'emplacement où insérer reste de l'ordre de n²/4, la méthode de recherche par dichotomie ne pouvant pas être appliquée à des listes.
