Tri par insertion

Le tri par insertion fonctionne de manière orthogonale par rapport au tri par bulles. Au lieu de parcourir l'ensemble tout entier pour trouver l'élément le plus grand, il insère un élément à la fois dans un sous-ensemble déjà trié.

Cet algorithme est utile lorsque l'ensemble des éléments n'est pas disponbile immédiatement. Imaginons par exemple une application interactive où l'utilisateur fournit un élément à la fois, qui doit maintenir un ensemble trié de ces éléments. Pour chaque élément fourni, la complexité est $O(n)$ ce qui est plus rapide que d'utiliser un algorithme $O(n \texttt{log} n)$.

Comme l'algorithme de tri par bulles, celui-ci s'applique aussi bien aux vecteurs qu'aux listes et avec la même complexité.