Le principe de ce tri est très simple: c'est le tri que toute personne utilise naturellement quand elle a des dossiers (ou n'importe quoi d'autre) à classer. On prend un dossier et on le met à sa place parmi les dossiers déjà triés. Puis on recommence avec le dossier suivant.

Pour procéder à un tri par insertion, il suffit de parcourir une liste : on prend les éléments dans l'ordre. Ensuite, on les compare avec les éléments précédents jusqu'à trouver la place de l'élément qu'on considère. Il ne reste plus qu'à décaler les éléments du tableau pour insérer l'élément considéré à sa place dans la partie déjà triée.

En Pascal

const MAX = 100;
type tab = array [1..MAX] of integer;


Procedure TriInsertion(n : integer ; var t : tab);
var i, j, k : integer;
begin
   for i:=2 to n do begin

       k := t[i]; (* k est la valeur à insérer *)
                  (* dans l'endroit approprié du tableau *)
   
       (* On décale toutes les valeurs du tableau < k *)
       (* à droite pour vider une place pour k        *)
       j := i - 1;
       while (j >= 1) and (t[j] > k) do begin

           t[j + 1] := t[j];
           j := j - 1;
       end;

       (* finalement la valeur k est insérée à son emplacement adéquat *)
       t[j + 1] := k;
   end;
end;

En C

#define MAX 100
 
void insertion(int t[MAX]) 
{
    /* Spécifications externes : Tri du tableau t par insertion séquentielle */
    int i,p,j,x;
 
    for (i = 1 ; i < MAX ; i++) 
    {

        /* Calcul de la position d'insertion p : */
        /* détermine le plus petit indice p       / 0 <= p <= i */
        /* qui vérifie t[p] >= t[i] */
        p = 0;
        while (t[p] < t[i]) 
            p++;
 
        x = t[i]; /* Sauvegarde de t[i] */

 
        for (j = i-1 ; j >= p  ; j--) 
            t[j+1] = t[j]; /* translation de t[p..i-1] vers t[p+1..i] */
 
        t[p] = x; /* insertion de t[p] */
    }
}

En Caml

let rec insere elem = function
    [] -> [elem]
  | tete::queue ->
      if elem < tete
      then elem::tete::queue            (* on a trouvé la place de l'élément *)

      else tete :: (insere elem queue)  

(* on continue à chercher dans la queue de la liste *)

let rec tri_insertion = function
    [] -> []
  | tete::queue -> insere tete (tri_insertion queue)