L'algorithme de tri par insertion marche sur les tableaux mais pas sur les listes. Avant l'itération k, les éléments 0 .. k sont dans l'ordre croissant, alors que les éléments k+1 .. n-1 n'ont pas été traités. Initialement, k=0.
À chaque itération, l'élément k+1 est déplacé dans une variable temporaire, ce qui libère la place numéro k+1. Puis, une comparaison entre l'élément numéro k et l'élément dans la variable temporaire est effectuée. Si l'élément numéro k est le plus petit des deux, alors l'itération se termine et le contenu de la variable temporaire est stocké à la place k+1. Sinon, on déplace l'élément k à la place k+1, ce qui libère la place k et on itère avec une comparaison entre l'élément k-1 et le contenu de la variable temporaire.
Le tri par insertion nécessite un nombre d'opérations proportionnel à n2 au pire. Si, par contre, les éléments sont déjà triés, alors, il ne nécessite que O(n) opérations. C'est également le cas si les éléments sont presque triés, à savoir qu'il y a un petit nombre d'élément qui ne respectent pas l'ordre croissant.
Le tri par insertion parcours potentiellement un grand nombre d'éléments à chaque itération, ce qui peut provoquer un grand nombre de défauts de cache.
Le tri par insertion est intrinsèquement séquentiel est donc difficile à paralléliser.