#include <stdio.h>
#include <stdlib.h>

#define taille 6400000

int tab[taille];

void fusion(int tableau[],int deb1,int fin1,int fin2)
{
  int *table1;
  int deb2=fin1+1;
  int compt1=deb1;
  int compt2=deb2;
  int i;
		
  table1=malloc((fin1-deb1+1)*sizeof(int));

  for(i=deb1;i<=fin1;i++)
    {
      table1[i-deb1]=tableau[i];
    }
		                
  for(i=deb1;i<=fin2;i++)
    {        
      if (compt1==deb2) 
	{
	  break; 
	}
      else if (compt2==(fin2+1)) 
	{
	  tableau[i]=table1[compt1-deb1]; 
	  compt1++;
	}
      else if (table1[compt1-deb1]<tableau[compt2])
	{
	  tableau[i]=table1[compt1-deb1]; 
	  compt1++;
	}
      else
	{
	  tableau[i]=tableau[compt2]; 
	  compt2++;
	}
    }
  free(table1);
}
        

void tri_fusion_bis(int tableau[],int deb,int fin)
{
  if (deb!=fin)
    {
      int milieu=(fin+deb)/2;

      tri_fusion_bis(tableau,deb,milieu);
      tri_fusion_bis(tableau,milieu+1,fin);
      fusion(tableau,deb,milieu,fin);
    }
}

void tri_fusion(int tableau[],int longueur)
{
  if (longueur>0)
    {
      tri_fusion_bis(tableau,0,longueur-1);
    }
}

     
int verif_tri()
{
  int i,prec;	
  prec=tab[0];
  i=1;
	
  while (i<taille && tab[i]>=prec)
    {	
      prec=tab[i];			
      i++;
    }	
  if (i==taille) 
    return 1;
  else
    return 0;
}

//programme qui permet de tester le tri fusion

int main()
{
  int i ,trie;
  int iter = 0 ;
  srand(time(0));       
      
  while (1)
    {
      printf("init Sort number %d ", iter);
      fflush (stdout) ;
      for(i=0;i<taille;i++)
	{
	  tab[i]=rand();		
	}
      printf(" sorting data ");
      fflush (stdout) ;
      tri_fusion(tab,taille);	
      printf(" checking ");
      fflush (stdout) ;
      trie=verif_tri();
			
      if (trie == 0)
	printf(" unsorted table \n");
      else 
	printf(" sorted table \n");

      fflush (stdout) ;
      iter++ ;
      sleep (5) ;
    }

}