/* Le 31.10.2007 par Valentin SCHMITT */

#include <stdio.h>
#include <stdlib.h>
#define MAX 511
int * S;

void fusion(int* T, int p, int q, int r) {
     int i,j,k;
     i=p;
     j=q+1;
     k=p;
     while((i<=q) && (j<=r)) {
          if(T[i] <= T[j]) {
               S[k]=T[i];
               i++;
               }
          else {
               S[k]=T[j];
               j++;
               }
          k++;
          }
     while(i<=q) {
          S[k]=T[i];
          i++;
          k++;
          }
     while(j<=r) {
          S[k]=T[j];
          j++;
          k++;
          }
     for(k=p;k<=r;k++)
          T[k]=S[k];
     }
     
void tri_fusion(int* T, int p, int r) {
     int q;
     if(p<r){
          q=(p+r)/2;
          tri_fusion(T,p,q);
          tri_fusion(T,q+1,r);
          fusion(T,p,q,r);
          }
     }

int * randtable(int n) {
     int i,* res;
     res=(int *) malloc(n*sizeof(int));
     for(i=0;i<n;i++)
          res[i]=random()%MAX;
     return res;
     }
     
int check(int * t, int n) {
     int i;
     for(i=0;i<n-1;i++)
          if(t[i]>t[i+1]) return (0);
     return (1);
     }

void print(int * T, int n) {
     int i;
     for(i=0;i<=n;i++)
          printf("T[%d]=%d\n",i,T[i]);
     }

int main(int argc, char* argv[]) {
     int n,* T;
     n=atoi(argv[1]);
     T=randtable(n);
     S=(int *) malloc(sizeof(int)*n);
/*     print(T,n);*/
     tri_fusion(T,0,n);
/*     print(T,n);*/
     if(!check(S,n))
          printf("Erreur: Tableau non trié !\n");
     
     free(S);
     free(T);
     return(0);
     }