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 ce qui est plus rapide
que d'utiliser un algorithme
.
Comme l'algorithme de tri par bulles, celui-ci s'applique aussi bien aux vecteurs qu'aux listes et avec la même complexité.