Principe de l'algorithme

L'idée du tri par insertion est la suivante: supposons que l'on ait un tableau trié jusqu'à l'élément $i-1$. Pour créer un tableau trié jusqu'à $i$ il suffit d'insérer l'élément $i$ à la bonne position dans la partie déjà triée (c'est à dire entre les indices 0 .. $i-1$). Après insertion le tableau est bien trié jusqu'à l'élément i.

Le tri par insertion a ici une définition récursive: pour résoudre le problème au rang $i$ on utilise le rang $i-1$.

Cet algorithme peut être décomposé en trois étapes:

1. appel récursif afin de résoudre le problème de taille $i-1$. Le tableau est donc supposé trié jusqu'à l'élément $i-1$ après cet appel.
2. recherche de la position où insérer l'élément $i$, appelée le rang de $i$ (ne pas confondre avec le ``rang'' de la récursion !)
3. insertion de l'élément dans la partie triée du tableau.

A la fin de ces trois étapes, le tableau est trié jusqu'à l'élément i.

Le tri par insertion est ainsi décomposé en deux autres algorithmes:

• l'algorithme Rang qui cherche où insérer l'élément $i$,
• l'algorithme Insertion aussi appelé Rotation qui insère l'élément dans la partie déja triée en décalant les autres éléments si nécessaire.