#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#if 1
typedef int element;
#define format_element "%d"
#else
typedef double element;
#define format_element "%lf"
#endif
void tri_a_bulle(element *tab, int taille)
{ int i,j;
  for(i=0;i<taille;i++)
  for(j=0;j<taille-1;j++)
  if(tab[j]>tab[j+1])
  { element x=tab[j]; tab[j]=tab[j+1]; tab[j+1]=x; }
}
void tri_a_bulle2(element *tab, int taille)
{ int j,encore;
  do
  { encore=0;
    for(j=0;j<taille-1;j++)
    if(tab[j]>tab[j+1])
    { element x=tab[j]; tab[j]=tab[j+1]; tab[j+1]=x; encore=1; }
  } while(encore);
}
void tri_a_bulle3(element *tab, int taille)
{ int j,nt;
  for(;taille>1;taille=nt)
  { nt=0;
    for(j=0;j<taille-1;j++)
    if(tab[j]>tab[j+1])
    { element x=tab[j]; tab[j]=tab[nt=j+1]; tab[j+1]=x; }
  }
}
void tri_selection(element *tab, int taille)
{ int i,j;
  for(i=0;i<taille;i++)
  { element x=tab[i];
    for(j=i+1;j<taille;j++) if(tab[j]<x)
    { tab[i]=tab[j]; tab[j]=x; x=tab[i]; }
  }
}
void tri_insertion(element *t, int taille)
{ int i, j;
  for(i=1;i<taille;i++)
  { element x=t[i];
    for(j=i-1;j>=0 && t[j]>x;j--) t[j+1]=t[j];
    t[j+1]=x;
  }
}
int partition1(element t[], int debut, int fin, int ipiv)
{ element pivot=t[ipiv], x;
  t[ipiv]=t[fin];
  int i, j;
  for(i=j=debut;i<fin;i++) if(t[i]<pivot)
  { x=t[i]; t[i]=t[j]; t[j++]=x; }
  t[fin]=t[j]; t[j]=pivot;
  return j;
}
int partition2(element t[], int debut, int fin, int ipiv)
{ element pivot=t[ipiv], x;
  t[ipiv]=t[fin];
  int i=debut, j=fin-1;
  while(i<j)
  { while(i<j && t[i]<=pivot) i++;
    while(i<j && t[j]>=pivot) j--;
    x=t[i]; t[i]=t[j]; t[j]=x;
  }
  if(t[j]<pivot) j++;
  t[fin]=t[j]; t[j]=pivot;
  return j;
}
int partition3(element t[], int debut, int fin, int ipiv)
{ element pivot=t[ipiv];
  t[ipiv]=t[fin]; t[fin]=pivot;
  int i=debut-1, j=fin;
  while(1)
  { while(t[++i]<pivot) ;
    if(i==j) return j;
    t[j]=t[i]; t[i]=pivot;
    while(t[--j]>pivot) ;
    if(i==j) return j;
    t[i]=t[j]; t[j]=pivot;
  }
}
int (*partition)(element t[], int, int, int)=partition1;
void tri_rapide(element t[], int debut, int fin)
{ if(debut<fin)
  { int j=partition(t,debut,fin,1?(debut+fin)/2:debut+rand()%(fin-debut+1));
    tri_rapide(t,debut,j-1);
    tri_rapide(t,j+1,fin);
  }
}
void tri_rapide1(element t[], int n) { partition=partition1; tri_rapide(t,0,n-1); }
void tri_rapide2(element t[], int n) { partition=partition2; tri_rapide(t,0,n-1); }
void tri_rapide3(element t[], int n) { partition=partition3; tri_rapide(t,0,n-1); }

void fusion1(element t[/*n*/], element u[/*m*/], element v[/*n+m*/], int n, int m)
{ int i=0, j=0;
  while(i<n && j<m)
  if(t[i]<u[j]) v[i+j]=t[i], i++;
  else          v[i+j]=u[j], j++;
  while(i<n)    v[i+j]=t[i], i++;
  while(j<m)    v[i+j]=u[j], j++;
}
void fusion2(element t[/*n*/], element u[/*m*/], element v[/*n+m*/], int n, int m)
{ int i=0, j=0, k=0;
  while(i<n && j<m) v[k++]=t[i]<u[j]? t[i++] :u[j++];
  while(i<n       ) v[k++]=           t[i++]        ;
  while(       j<m) v[k++]=                   u[j++];
}
void fusion3(element t[/*n*/], element u[/*m*/], element v[/*n+m*/], int n, int m)
{ int i=0, j=0;
  while(i<n && j<m) *v++=t[i]<u[j]? t[i++] :u[j++];
  while(i<n       ) *v++=           t[i++]        ;
  while(       j<m) *v++=                   u[j++];
}
void fusion4(element t[/*n*/], element u[/*m*/], element v[/*n+m*/], int n, int m)
{ while(n && m) *v++=*t<*u? n--,*t++ :(m--,*u++);
  while(n     ) *v++=*t++,n--;
  while(     m) *v++=*u++,m--;
}
void (*fusion)(element*,element*,element*,int,int)=fusion4;
void tri_fusion(element t[/*n*/], int n)
{ int m=n/2, p=n-m;
  if(!m) return;
  tri_fusion(t,m);
  tri_fusion(t+m,p);
  element u[m];
  int i;
  for(i=0;i<m;i++) u[i]=t[i];
  fusion(u,t+m,t,m,p);
}
int min(int a, int b) { return a<b? a :b; }
void tri_fusion_ite(element t[], int n)
{ element u[n], *a=t, *b=u, *c;
  int l, i, j;
  for(l=1;l<n;l+=l)
  { for(i=0;i+l+l<n;i+=l+l) fusion(a+i,a+i+l,b+i,l,l);
    j=min(n-i,l);
    fusion(a+i,a+i+l,b+i,j,n-i-j);
    c=a, a=b, b=c;
  }
  if(a!=t) for(i=n;i--;) t[i]=a[i];
}
void tri_fusion1(element*t, int n) { fusion=fusion1; tri_fusion(t,n); }
void tri_fusion2(element*t, int n) { fusion=fusion2; tri_fusion(t,n); }
void tri_fusion3(element*t, int n) { fusion=fusion3; tri_fusion(t,n); }
void tri_fusion4(element*t, int n) { fusion=fusion4; tri_fusion(t,n); }
void tri_fusion_ite1(element*t, int n) { fusion=fusion1; tri_fusion_ite(t,n); }
void tri_fusion_ite2(element*t, int n) { fusion=fusion2; tri_fusion_ite(t,n); }
void tri_fusion_ite3(element*t, int n) { fusion=fusion3; tri_fusion_ite(t,n); }
void tri_fusion_ite4(element*t, int n) { fusion=fusion4; tri_fusion_ite(t,n); }
void afft(element t[], int n)
{ while(n--) printf(" "format_element,*t++);
  printf("\n");
}
int croissant(element t[], int n)
{ for(;n>1;n--) if(t[n-2]>t[n-1]) return 0;
  return 1;
}
element somme(element t[], int n)
{ element s=0;
  while(n) s+=t[--n];
  return s;
}
typedef void (*tri)(element*,int);
void test(element t[],int n,tri f,const char *nom)
{ element *u=malloc(n*sizeof(*u));
  int i;
  for(i=n;i--;) u[i]=t[i];
  int a=clock();
  f(u,n);
  a=clock()-a;
  printf("%s trie %s %d nombres en un temps de %d/%ds\n",
     nom,croissant(u,n) && somme(t,n)==somme(u,n)?"bien":"mal",n,a,(int)CLOCKS_PER_SEC);
  free(u);
}
#define testri(t,n,tri) test(t,n,tri,#tri)
void taleat(element t[], int n)
{ int i;
  for(i=n;i--;) t[i]=i*i%(2*n+1);
}
int main()
{ element t[]={21, 2, -1, 7, 4, 18, 3, 9, 23, 0, 1, 14, -5}, n=13;
  afft(t,n);
  tri_insertion(t,n);
  afft(t,n);
  for(n=1;n<=1000000;n*=10)
  { element *t=malloc(n*sizeof(*t));
    taleat(t,n);
    testri(t,n,tri_rapide1);
    testri(t,n,tri_rapide2);
    testri(t,n,tri_rapide3);
    testri(t,n,tri_fusion1);
    testri(t,n,tri_fusion2);
    testri(t,n,tri_fusion3);
    testri(t,n,tri_fusion4);
    testri(t,n,tri_fusion_ite1);
    testri(t,n,tri_fusion_ite2);
    testri(t,n,tri_fusion_ite3);
    testri(t,n,tri_fusion_ite4);
    if(n>10000) continue;
    testri(t,n,tri_a_bulle);
    testri(t,n,tri_a_bulle2);
    testri(t,n,tri_a_bulle3);
    testri(t,n,tri_selection);
    testri(t,n,tri_insertion);
    free(t);
  }
  return 0;
}