Tri insertion par méthode récursive

Voici une procédure récursive qui permet de trier un tableau de n entiers en utilisant la méthode de tri par insertion :
Procedure Tri_Ins (Var t: TAB; n: integer);
Var aux,i : integer;
begin
If n > 1 Then
begin
Tri_Ins (t,n - 1);
If t[n] < t[n - 1] Then
Begin
aux:= t[n];
i := n;
Repeat
t[i] := t[i - 1];
i := i - 1;
Until (i = 1) Or (aux > t[i - 1]);
t[i] := aux;
End;

Bonjour,

Je vois la chose un peu comme la récursivité vue en math: On suppose que le résultat d'un appel est un tableau déjà trié
Ensuite on cherche dans ce tableau trié où insérer une valeur

ainsi en pseudo code je verrais une chose du style:

sort ( tab )
{
   // Cas d'arrêt :
   si taille du tableau est 0 alors il est trié (on pourrait s'arrêter à 1 mais on gère ainsi le cas ou le tableau original est vide)
   End

   sinon:
   // garder une des valeurs du tableau (par exemple la première)
   var valeur = tab[0]

   // trier le reste du tableau
   sort ( tab + 1 )   // où tab + 1 est le tableau à partir de la 2me case

   // Insérer valeur dans le tableau maintenant trié
   tant que valeur est <comparaison voulue> par rapport à tab[i]
   augmenter l'indice jusqu'à trouver où insérer valeur

   //   On a trouvé l'indice où mettre valeur
   décaler tous les éléments à partir de i (i compris)
   mettre valeur à l'indice i
   End
}

Je ne vois pas de solution sans décaler chaque fois tous les éléments. Cela reste de l'insertion.

On passera aussi en paramètre la taille du tableau si le langage d'implémentation ne permet pas de la déduire de la variable tab.
avec alors une récursivité sort ( tab + 1, taille - 1 )

M.