Tri par insertion à sélection dichotomique¹

Dans cette version du tri par insertion, le Rang de $val$ est cherché par dichotomie: l'idée est de cerner la position d'insertion en coupant en deux l'espace de recherche à chaque appel récursif. La figure 1.3.2 illustre ce principe.

Algorithme Rang
Input:
  int N;
  int tbl[N];
  int g;
  int d;
  int val;
Output:
  int
Begin
  int m;

  if (g == d)
    return (g);
  else
  {
    m=(g+d)/2; // division sur entiers
    if (tbl[m] > val)
       return (Rang(N,tbl,g,m,val));
    else
       return (Rang(N,tbl,m+1,d,val));
  }
End

Complexité (comparaisons) en $\Theta(log(n))$.
Complexité (comparaisons) de TriInsertion en $O(n log(n))$.
Complexité (accès) de TriInsertion en $\theta(n^2)$.