#include<stdio.h>
int t[]={25,0,4,7,3,15},
 suiv[]={-1,0,0,5,2,4 };     
void aff(int l)    //  affiche la liste chaînée t[l] t[suiv[l]] t[suiv[suiv[l]]] etc.
{ while(l>=0) printf(" %d",t[l]), l=suiv[l];
  printf("\n");
}
int retourne(int l1)
{ int l2=-1;              //  l2= liste vide
  while(l1>=0)            //  tant que l1 n'est pas vide
  { int p=l1; l1=suiv[p]; //     on enlève le premier maillon de l1, en le mettant dans p
    suiv[p]=l2; l2=p;     //     on ajoute le maillon p en tête de l2
  }
  return l2;              //  la liste l2 contient tous les maillons initialement dans l1 mais dans l'ordre inverse
}
int fusion(int l1,int l2) // fusionne les deux listes chaînées triées l1 et l2 en une liste triée
{ return
  l1<0?l2:                // si l1 est vide on rend l2
  l2<0?l1:                // si l2 est vide on rend l1
  t[l1]<=t[l2]?suiv[l1]=fusion(suiv[l1],l2),l1:  // on rend le premier maillon de l1 suivi de la fusion de l2 et du reste de l1
  fusion(l2,l1);          // on échange l1 et l2 
}
int fusion2(int l1,int l2)// version itérative de fusion
{ int *r=&l1;             // r=&l1 donc *r=l1 et la boucle suivant a pour effet l1=fusion(l1,l2)
  // la boucle suivante à pour effet *r=fusion(*r,l2) mais *r représente d'abord l1 puis des cases du tableau suiv                  
  while(l2>=0)            // si l2 est vide, il n'y a plus rien à faire
   if(*r>=0 && t[*r]<=t[l2]) r=suiv+*r; // Dans ce cas il suffit de faire  suiv[*r]=fusion(suiv[*r],l2) et donc r=&suiv[*r]
   else {int p=*r; *r=l2, l2=p;}  // fusion(*r,l2) = fusion(l2,*r)
  return l1;              // puisque la boucle précédente a fait l1=fusion(l1,l2)
}
int tri(int l)
{ int l1=-1, l2=-1;            // l1=l2=liste vide
  while(l>=0)                  // Tant que l n'est pas vide
  { int p=l; l=suiv[p],        // on enlève le premier maillon de l, en le mettant dans p,
    suiv[p]=l1, l1=l2, l2=p;   // on le met en tête de l1, puis on échange l1 et l2
  }
  // Les deux listes l1 et l2 contiennent chacune la moitié des maillons de l, mais l2 en a peut-être un de plus.
  return l1<0?l2               // si l1 est vide, alors l2 a au plus un élément et est donc trié.
             :fusion2(tri(l1),tri(l2)); // sinon on trie chacune des deux moitiés puis on les fusionne
}
int main()
{ int l=3;
  aff(l);   //  7 15 3 4 25    =t[3] t[5] t[4] t[2] t[0]   car suiv[3]=5 suiv[5]=4 suiv[4]=2 suiv[2]=0 suiv[0]=-1
  l=retourne(l);
  aff(l);   //  25 4 3 15 7    =t[0] t[2] t[4] t[5] t[3]   car suiv[0]=2 suiv[2]=4 suiv[4]=5 suiv[5]=3 suiv[3]=-1
  l=tri(l);
  aff(l);   //  3 4 7 15 25    =t[4] t[2] t[3] t[5] t[0]   car suiv[4]=2 suiv[2]=3 suiv[3]=2 suiv[5]=0 suiv[0]=-1
  return 0;
}