Réponse :
Son principe est de parcourir la liste non triée (a1, a2, ... , an) en la décomposant en deux parties une partie tdéjà triée et une partie non triée. La méthode est identique à celle que l'on utilise pour ranger des cartes que l'on tient dans sa main : on insère dans le paquet de cartes déjà rangées une nouvelle carte au bon endroit. L'opération de base consiste à prendre l'élément frontière dans la partie non triée, puis à l'insérer à sa place dans la partie triée (place que l'on recherchera séquentiellement), puis à déplacer la frontière d'une position vers la droite. Ces insertions s'effectuent tant qu'il reste un élément à ranger dans la partie non triée.. L'insertion de l'élément frontière est effectuée par décalages successifs d'une cellule.
La liste (a1, a2, ... , an) est décomposée en deux parties : une partie triée (a1, a2, ... , ak) et une partie non-triée (ak+1, ak+2, ... , an); l'élément ak+1 est appelé élément frontière (c'est le premier élément non trié).
Explications :
