/* 
 * Le 31.10.2007, tri fusion par Valentin SCHMITT 
 */
#include "table.c"


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);
          }
     }

void  test ( void )
  {
  int n, *T;
  printf("\nVerification : ");
  for ( n = pas; n < nmax; n += pas ) {
    printf("\ntaille:%d", n);
    T = randtable( n );
    S = (int *) malloc(sizeof(int) * n); 
    printable( T, n);
    tri_fusion(T, 0, n - 1); 
    printable( T, n);
    if( ! verification( T , n) )
           printf("\nErreur: Tableau non trié !");
    free( S ); free( T );
  }  
  printf("\neot...\n");
  exit (0 ); 
  }


void testsortdata( void )
  {
  int n, *T;
  time_t deb, fin;
  double fc=0;
  printf("\nTemps de calcul table en ordre : ");
  pas = nmax / nblignes;
  for ( n = pas; n <= nmax; n += pas ) {
    T = sorttable( n );
    S = (int *) malloc(sizeof(int) * n); 
    deb = time( NULL );
    tri_fusion(T, 0, n - 1); 
    fin = time( NULL );
    fc += difftime( fin, deb )/n/log(n);
    printf("\nn= %d duree= %.2f ", n, difftime( fin, deb )  );
    free( S ); free( T );
  }
  printf("\nfacteur cache : %e\n", fc/nblignes);
  exit(0); 
  }

void testranddata( void )
  {
  int n, *T;
  time_t deb, fin;
  double fc; 
  printf("\nTemps de calcul table aleatoire : ");
  for ( n = pas; n <= nmax; n += pas ) {
    T = randtable( n );
    S = (int *) malloc(sizeof(int) * n); 
    deb = time( NULL );
    tri_fusion(T, 0, n - 1); 
    fin = time( NULL );
    fc += difftime( fin, deb )/n/log(n);
    printf("\nn= %d duree= %.2f", n, difftime( fin, deb ) ); 
    free( S ); free( T );
  }
  printf("\nfacteur cache : %e\n", fc/nblignes);
  exit(0); 
  }


int main (int argc ,char*argv[])
  {

  options( argc,argv );

  if ( check ) test ();
  if (   randopt ) testranddata(); 
  if ( ! randopt ) testsortdata();
 
  return 0; 
  }