Implémentation récursive

Algorithme TriInsertion
Input:
  int N;                   // N > 0
  int tbl[N];              // modifié
  int i;                   // trie le tableau de 0 a i  
                           //      => premier appel: TriInsertion(N,tbl,N-1)
Output:
  // pas de retour: modification directe du tableau
Begin
  if (i > 0)
  {
    // appel récursif pour trier de 0 à i-1
    TriInsertion(N,tbl,i-1);
    // si l'élément i n'est pas à la bonne place (si il n'est
    // pas le max du tableau déjà trié)
    if (tbl[i] < tbl[i-1])
    {
      // Cherche la place ou devrait etre i dans le tableau deja trie
      k=Rang(N,tbl,0,i-1,tbl[i]);
      // Insere i
      Insertion(N,tbl,i,k);
    }
  }
End