#include<stdio.h>
#include<stdlib.h>
#include<time.h>
const int bavard=0;
int *allocation(int taille) { return malloc(taille*sizeof(int)); }
void remplir_tableau(int *t, int n, int min, int max)
{ while(n) t[--n]=min+rand()%(max-min+1); }
void afft(int *t,int n)
{ while(n--) printf("%d ",*t++); printf("\n"); }
void afft10(int*t,int n) { afft(t,n<10?n:10); }

int est_trie(int *t, int n)
{ while(--n>0) if(t[n]<t[n-1]) return 0;
  return 1;
}
int egaux(int*t,int*u,int n)
{ for(int i=0;i<n;i++) if(t[i]!=u[i]) return 0;
  return 1;
}
void tri_insertion(int*t,int n)
{ for(int i=0,j,x;++i<n;t[j]=x)
   for(x=t[j=i];j && t[j-1]>x;j--) t[j]=t[j-1];
}
void tri_bulle(int*t,int n)
{ int i,k,x;// k est la position du dernier élément déplacé.
  for(;n>1;n=k)      // Tant qu'il y a plusieurs nombres à trier
   for(i=k=1;i<n;i++)// une bulle parcourt tout le tableau.
    if(t[i]<t[i-1])//Deux éléments consécutifs sont éventuellement
     x=t[k=i],t[i]=t[i-1],t[i-1]=x;  // échangés.
} // Les éléments au delà de k sont à leur place définitive et
  // sont donc exclus du tri par n=k.
void tri_base256(int*t,int n) // drapeau américain
{ int tt[n], *u=tt, *v, e[256], i, j, l, c, m;
  for(l=0;l<8*sizeof(int);l+=8)
  { m=~(~0u>>1)>>l&255; // m est inutile si *t n'est pas signé.
    for(j=0;j<256;j++) e[j]=0; // mise à 0 des 256 compteurs
    for(i=0;i<n;i++) e[t[i]>>l&255]++; // comptage
    for(c=n,j=256;j--;) e[j^m]=c-=e[j^m]; // empilage des seaux
    for(i=0;i<n;i++) u[e[t[i]>>l&255]++]=t[i];// tri stable selon un chiffre
    v=u,u=t,t=v; // t et tt sont échangés.(sizeof(int) est pair)
  }
}
void tri_comptage(int*t,int n)
{ if(n<2) return;
  int i, j, min=*t, max=*t;
  for(i=1;i<n;i++) if(t[i]<min) min=t[i]; else
                   if(t[i]>max) max=t[i];
  int l=max-min+1, c[l], k=0;
  for(j=0;j<l;j++) c[j]=0; // Tous les compteurs sont mis à 0.
  for(i=0;i<n;i++) c[t[i]-min]++; // c[j] compte les min+j
  for(j=0;j<l;j++) while(c[j]) c[j]--,t[k++]=j+min;
}
void tri_cycle(int*t,int n)
{ if(n<2) return;
  int i, j, min=*t, max=*t, s=0, x, y;
  for(i=1;i<n;i++) if(t[i]<min) min=t[i]; else
                   if(t[i]>max) max=t[i];
  int l=max-min+1, c[l];
  for(j=0;j<l;j++) c[j]=0; // Tous les compteurs sont mis à 0.
  for(i=0;i<n;i++) c[t[i]-min]++; // c[j] compte les min+j
  for(j=0;j<l;j++) s=c[j]+=s;
  for(i=0;i<n;i++) // Chaque elément
   if(x=t[i],c[x-min]>i) // qui n'a pas encore été mis à sa place
    do y=t[j=--c[x-min]], t[j]=x, x=y;  while(j!=i); // débute un cycle de permutations.
}
void tri_bingo(int*t, int n)
{ while(n>1)
  { int m=*t, i;
    for(i=1;i<n;i++) if(t[i]>m) m=t[i]; // m est la plus grande valeur du tableau
    for(i=n;i;) if(t[--i]==m) t[i]=t[--n],t[n]=m; // Tous les m sont mis à la fin
  }
}
int Partition(int*t,int j)
{ int i=j/2, p=t[i];     // On prend le pivot au milieu.
  for(t[i]=*t,*t=p,i=0;;)// On l'échange avec le premier élément.
  {
    while(t[--j]>p) ;    // Un petit élément en fin de tableau
    if(i==j) return i;
    t[i]=t[j], t[j]=p;   // est échangé avec le pivot.
    while(t[++i]<p) ;    // Un grand élément en début de tableau
    if(i==j) return i;
    t[j]=t[i], t[i]=p;   // est échangé avec le pivot.
  } // Un élément égal au pivot passe toujours de l'autre coté.
} /* Ainsi le pivot sert de sentinelle (on ne teste pas i<j
  dans les while). De plus si par exemple tous les éléments du
  tableau son égaux, alors la partition est en 2 parts égales.*/
void tri_rapide(int*t,int n)
{ for(int p;n>1;n=p) p=Partition(t,n),tri_rapide(t+p+1,n-p-1); }
void tri_rapid(int*t,int n)// ne trie pas les petits sous-tableaux
{ for(int p;n>5;n=p) p=Partition(t,n),tri_rapid(t+p+1,n-p-1); }
void tri_rapi(int*t,int n) { tri_rapid(t,n),tri_insertion(t,n); }
void Fusion(int*t,int n,int m)
{ int u[n], *v=t+n, i, j, k;     // t[n+m]=t[n]+v[m]
  for(i=0;i<n;i++) u[i]=t[i];    // t[n+m]=u[n]+v[m]
  for(i=j=k=0;i<n && j<m;) t[k++]=v[j]<u[i]? v[j++] :u[i++];
  while(i<n) t[k++]=u[i++];
}
void fusion(int*tab, int d, int m, int f) { Fusion(tab+d,m-d+1,f-m); }
void merge_sort(int*tab,int d,int f)
{ if(d>=f) return;
  int m=(d+f)/2;
  merge_sort(tab,d,m);
  merge_sort(tab,m+1,f);
  fusion(tab,d,m,f);
}
void tri_merge(int*t,int n) { merge_sort(t,0,n-1); }
int croi=0;  // croi=1 si le tableau tend à croitre
void fusi(int*t,int n,int m) // recherche dichotomique
{ if(!croi) return Fusion(t,n,m); // éventuelle
  if(!n || !m) return;  // du premier t[i] qui doit bouger    
  int i=0, j, k=n, x=t[n];    //  pour minimiser n 
  while(i<k) if(t[j=(i+k)/2]>x) k=j; else i=j+1;
  Fusion(t+i,n-i,m);
}
void tri_fusion(int*t,int nm)
{ if(nm<6) return tri_insertion(t,nm);
  int n=nm/2, m=nm-n, *v=t+n;
  tri_fusion(t,n); // trie la première moitié
  tri_fusion(v,m); // trie la deuxième moitié
  fusi(t,n,m);   // fusionne les 2 moitiés déjà triées
}
int min(int a,int b) { return a<b?a:b; }
void tri_fusion_ite(int*t,int n)
{ int i, j, l=5;
  for(i=0;i+l<n;i+=l) tri_insertion(t+i,l);
  tri_insertion(t+i,n-i);
  for(;l<n;l+=l)
   for(i=0;j=i+l,j<n;i=j+l)
    Fusion(t+i,l,min(l,n-j));
}
void retourne(int*t,int*u) {for(;t<--u;) {int x=*t; *t++=*u,*u=x;}}
void tri_tim(int *t, int n)
{ int pile[100], *p=pile+100, j, x, y, z;
  for(*--p=-3*n, *--p=-n, *--p=j=0;j<n;) // Le bas de la pile
  {            // contient deux suites virtuelles de longueur 2n,n
    while(++j<n && t[j-1]>t[j]) ;  // Une suite décroissante
    retourne(t+*p,t+j);            // est retournée puis
    while(j<n && t[j-1]<=t[j]) j++;// allongée
    *--p=j;                        // et mise dans la pile.
    while(x=j-p[1],y=p[1]-p[2],z=p[2]-p[3],x+y>z||x>y||(j==n&&x<n))
    if(x>z) fusi(t+p[3],z,y), p[2]=p[1], *++p=j;
    else    fusi(t+p[2],y,x),            *++p=j;
  }
}
/* La procédure précédente utilise une pile contenant des "runs".
Soient x, y et z les longueurs des 3 runs au sommet de pile. (x est au sommet).
On doit avoir x<=y<=z et x+y<=z. Sinon on fusionne y avec min(x,z).
Mais la pile va peut-être croitre et certains runs vont fusionner. Donc
x et y vont peut-être augmenter et on n'aura plus x+y<=z.
On peut modifier la procédure pour éviter cela. La procédure suivante utilise
deux piles. La première pile est le bas de l'ancienne pile. Trois runs
consécutifs de cette pile vérifient toujours x+y<=z et x<=y.
La deuxième pile est le haut de l'ancienne pile. On essaye de transférer son
sommet dans la première pile : *--p=j=*--q. Les deux piles sont aux deux extrémités du
tableau pile[].
Dans la pile on ne met pas la longueur d'un run mais l'indice de l'élément suivant le run
et j=*p est une copie du sommet de pile. Donc x=p[0]-p[1], y=p[1]-p[2], ... .
*/
void tri_tim2(int *t, int n)
{ int pile[100], *q=pile, *p=q+100, j, x, y, z;
  for(*--p=-3*n, *--p=-n, *--p=j=0;j<n;) // Le bas de la pile
  {            // contient deux suites virtuelles de longueur 2n,n
    while(++j<n && t[j-1]>t[j]) ;  // Une suite décroissante
    retourne(t+*p,t+j);            // est retournée puis
    while(j<n && t[j-1]<=t[j]) j++;// allongée
    for(*q++=j;q>pile;)            // et mise dans la pile.
    for(*--p=j=*--q;x=j-p[1],y=p[1]-p[2],z=p[2]-p[3],x+y>z||x>y||(j==n&&x<n);*++p=j)
    if(x>z) fusi(t+p[3],z,y), *q++=j, j=*++p;
    else    fusi(t+p[2],y,x);
  }
}
void tri_tas(int*t,int n)
{ int i,j,x,s=n/2;
  for(;n>1;t[i]=x,s-=!s? x=*t,*t=t[--n],t[n]=x,0 :1)
   for(x=t[i=s];j=2*i+1,j<n && t[j+=j+1<n && t[j+1]>t[j]]>x;i=j)
    t[i]=t[j];
}
void peigne(int*t,int n)
{ int h,i,j,x;
  for(h=n;h=h*10/13,h>1;)
   for(j=h;j<n;j++) if(t[i=j-h]>t[j]) x=t[i],t[i]=t[j],t[j]=x;
}
void tri_peigne(int*t,int n) {peigne(t,n),tri_bulle(t,n);}
void tri_peign (int*t,int n) {peigne(t,n),tri_insertion(t,n);}
void tri_shell_pratt(int*t,int n)
{ for(int h=n;h;h--)
   if(729*729*729%(h/(h&-h))==0) // si h=(2^a)*(3^b)
    for(int i=0,j;j=i+h,j<n;i++)
     if(t[i]>t[j])
      { int x=t[i]; t[i]=t[j], t[j]=x; }
}
void tri_stooge(int*t, int n)
{ if(n>2) { int m=2*(n+1)/3;
   tri_stooge(t,m),tri_stooge(t+n-m,m),tri_stooge(t,m); }
  else if(n>1 && *t>t[1])
  { int x=*t; *t=t[1], t[1]=x; }
}
void melange_aleatoire(int*t, int n)
{ while(n>1) {int j=rand()%n, x=t[--n]; t[n]=t[j], t[j]=x; }}
void tri_aleat(int*t, int n)
{ while(!est_trie(t,n)) melange_aleatoire(t,n); }
void ech(int*a,int*b) { int x=*a; *a=*b; *b=x;}
void tri_bete(int*t,int n)
{ int ok=0;
  void tri(int m)
  { if(m<=1) ok=est_trie(t,n); else
     for(int j=m--;j-- && !ok;) ech(t+m,m&1?t:t+j), tri(m);
  }
  tri(n);
}

typedef void tri_t(int*,int);
void test_tri(int*t, int*u, int*ut, int n, tri_t tri,char*nom)
{ if(bavard) afft10(t,n);
  for(int i=0;i<n;i++) u[i]=t[i];
  int a=clock();  // heure de début du tri
  tri(u,n);
  a=clock()-a;    // durée du tri = heure de fin - heure de début
  if(bavard) afft10(u,n);
  printf("%-15s(t,%7d) dure%8d%4s trié%5s\n",
           nom,    n,       a, est_trie(u,n)?"":"non",
                                  egaux(u,ut,n)?"bon":"faux");
}
void american_flag(int *t,int n)
{ typedef unsigned char (*t4)[4];
  int i,j,l,c[256],d[256],u[n],*v=u,*w;
  for(l=0;l<4;l++)  // choix du chiffre de poids 256^l
  { for(j=0;j<256;j++) c[j]=0;   // mise à zéro des 256 compteurs
    for(i=0;i<n;i++) c[((t4)t)[i][l]]++; // comptage (calcul des hauteurs des 256 piles)
    d[0]=0;
    for(j=0;j<255;j++) d[j+1]=d[j]+c[j]; // sommes partielles des compteurs (empilement des 256 piles)
    if(l==3) for(j=128;j--;) d[j]+=n-d[128], d[j+128]-=d[128]; // gestion du signe (échange des 128 piles du haut avec celles du bas)
    for(i=0;i<n;i++) v[d[((t4)t)[i][l]]++]=t[i]; // répartition dans les différentes piles
    w=t,t=v,v=w;    // échange de t et u
  }
}
void american_flag2(int *t,int n)
{ union { int v; unsigned char c[4]; } x;
  int i,j,l,c[256],d[256],u[n],*v=u,*w;
  for(l=0;l<4;l++)
  { for(j=0;j<256;j++) c[j]=0;
    for(i=0;i<n;i++) x.v=t[i],c[x.c[l]]++;
    d[0]=0;
    for(j=0;j<255;j++) d[j+1]=d[j]+c[j];
    if(l==3) for(j=128;j--;) d[j]+=n-d[128], d[j+128]-=d[128];
    for(i=0;i<n;i++) x.v=t[i], v[d[x.c[l]]++]=t[i];
    w=t,t=v,v=w;
  }
}
void nain_de_jardin(int*t,int n)
{ int i=0, x;
  while(i<n-1)
  { if(i<0) i=0;
    if(t[i]>t[i+1]) x=t[i],t[i]=t[i+1],t[i+1]=x, i--;
    else i++;
  }
}
void tri_shaker(int*t,int n)
{ int m=0, k=n-1, i, x;
  while(m<k) // Il faut trier t[m,m+1,...,k]
  { for(i=n=k;i>m;i--) if(t[i]<t[i-1]) x=t[i],t[k=i]=t[i-1],t[i-1]=x;
    for(i=m=k;i<n;i++) if(t[i]>t[i+1]) x=t[i],t[k=i]=t[i+1],t[i+1]=x;
  }
}
#define nom(tri_truc) tri_truc,#tri_truc // tri_chose,"tri_chose"
int main()
{ srand(time(0));
  for(int niv=3;niv--;)
  for(int n=10;n<=1000000;n*=10)
  { int *t=allocation(n*3), *u=t+n, *v=u+n, i;// int t[n],u[n],v[n];
    if(niv==2) for(i=0;i<n;i++) t[i]=rand()%n-n/3; else
    if(niv   ) for(i=0;i<n;i++) t[i]=rand();
    else       for(i=0;i<n;i++) t[i]=rand()%10+i;
    if(bavard) if(n<=200) afft(t,n);
    // tris en n
    test_tri(t,v,v,n,nom(tri_base256));
    if(niv!=1)
    test_tri(t,u,v,n,nom(tri_cycle)),
    test_tri(t,u,v,n,nom(tri_comptage));
    test_tri(t,u,v,n,nom(american_flag));
    test_tri(t,u,v,n,nom(american_flag2));
    // tris en n*ln(n)
    test_tri(t,u,v,n,nom(tri_rapi));
    test_tri(t,u,v,n,nom(tri_merge));
    for(croi=2;croi--;)
    test_tri(t,u,v,n,nom(tri_fusion)),
    test_tri(t,u,v,n,nom(tri_tim)),
    test_tri(t,u,v,n,nom(tri_tim2));
    test_tri(t,u,v,n,nom(tri_fusion_ite));
    test_tri(t,u,v,n,nom(tri_rapide));
    test_tri(t,u,v,n,nom(tri_tas));
    // tris en n*ln(n)*ln(n)
    test_tri(t,u,v,n,nom(tri_peign));
    test_tri(t,u,v,n,nom(tri_peigne));
    test_tri(t,u,v,n,nom(tri_shell_pratt));
    // tris en n*n  mais en n si le tableau est trié
    if(n<=10000 || !niv) test_tri(t,u,v,n,nom(tri_insertion)),
                         test_tri(t,u,v,n,nom(nain_de_jardin)),
                         test_tri(t,u,v,n,nom(tri_shaker)),
                         test_tri(t,u,v,n,nom(tri_bulle));
    // tri en n*(nombre de valeurs différentes) donc en O(n*n)
    if(n<=10000        ) test_tri(t,u,v,n,nom(tri_bingo));
    // tri en n^(ln 3/ln 1.5)
    if(n<= 1000        ) test_tri(t,u,v,n,nom(tri_stooge));
    // tri en n!
    if(n<=   10        ) test_tri(t,u,v,n,nom(tri_aleat)),
                         test_tri(t,u,v,n,nom(tri_bete));
    free(t);
  }
  return 0;
}