Cet algorithme utilise le même prinicpe que le tri par insertion sauf qu'il rajoute une petite optimisation: on va employer une recherche dichotomique pour la recherche de la position d'insertion, bien plus efficace.     

FUNCTION posit_ins ( var v : vec_t;
                                 i : integer;
                                 x : type_element) : integer;
      VAR inf, sup, m : integer;
      BEGIN
          { le cas des extrémités }
           if x < v[1] then posit_ins := 1
          else if v[i-1] <= x then posit_ins := i
          else begin
                 { init dichotomie : les cas 1 et i sont déjà traités }
                 inf := 2; sup := i-1;
                 { recherche position m tel que v[m-1] <= x < v[m] }
                 { : variante de la dichotomie habituelle,                 }
                 {   sans le booléen trouve                                     }
                 while inf < sup do
                 begin
                   m := (inf + sup) div 2;
                   if v[m] <= x
                   then inf := m+1
                   else sup := m;
                 end;
                 posit_ins := sup;
               end;
      END;

Le coût 

Méthode nettement plus efficace que les autres pour vn grand :
   La recherche dichotomique sur v[1..i] est en log 2 i. L’insertion dans v[1..i]
coute en moyenne i/2. Le cout total est donc vn (log2 i + i/2).
  Par exemple avec vn = 1000, le coût est de 10 000, contre 500 000 pour les autres tris.