#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#define MAX 500000

int mergeworse(int *p,int n)
{
 int *a,*a1,*a2,i;




 if(n>3)
  {
   if( (a=(int *) calloc((size_t) n,sizeof(int)) )==NULL )
         return 0;

   for(i=1,a1=a,a2=a+n/2; i<=n ;++i)
     {
      if(i%2==1)
        *(a1++)=*(p+i-1);
      else
        *(a2++)=*(p+i-1);

     }

   for(a1=p,a2=a; a1<p+n ;++a1,++a2)
        *a1=*a2;

   free(a);

   if( mergeworse(p,n/2)==0 || mergeworse(p+n/2,n/2 + n%2)==0 )
       return 0;

  }


 return 1;

}



int mergesort(int *p,int n,long double *syg)
{
	int *a,*a1,*a2,*a3;
	
	++(*syg);
	
	if(n>1)
	{
		if( (a=(int *) calloc((size_t) n,sizeof(int)))==NULL)
    		  { ++(*syg);   return 0; }
		else if(mergesort(p,n/2,syg)==0 || mergesort(p+n/2,n/2 + n%2,syg)==0 )
		{	(*syg)+=3;  return 0;	}	
		else
		{
			(*syg)+=3;
			for(a1=p,a2=p+n/2,a3=a ;  ; ++a3)
			{
				if(a1<p+n/2 && a2<p+n)
                   			 {
                			            (*syg)+=3;
             				            if(*a1<=*a2)
            				            {		 *a3=*(a1++);	}
				            else
                 				{      *a3=*(a2++);        }
                   			 }

				else if(a1<p+n/2)
                   			 {
                   				  (*syg)+=3;
                  				   *a3=*(a1++);
                 			 }
         			             else if(a2<p+n)
                                     	             {
            				                (*syg)+=4;
     				                *a3=*(a2++);
     			             }
            			            else
               		            {
                    				 (*syg)+=4;
               				  break;
          			            }

        		     }


     		  for(a1=p,a3=a; a1<p+n ;++a1,++a3,++(*syg))
       		  {	       *a1=*a3;	}


       free(a);

       return 1;
      }

   }

 return 1;

}






int main()

 {
        int *p;
        int i,n=MAX;
        long double syg=0;
        clock_t t2;
        time_t seed;
        long r;
	
	p=(int *)malloc(MAX+100000000);
        
	time(&seed);
	srand((long)seed);
	

       /* for(i=0;i<MAX;i++)
         {
              r=rand();
				*(p+i)=r;
         }
                */
         
         
   /*     for(i=0;i<MAX;i++)
        {
                printf("stoixeia pinaka %d\n",*(p+i));

       }	*/
        
        if(p!=NULL)
		{    mergeworse(p,n);  }  
        
        
        clock(); 
        if(p!=NULL)
		{       mergesort(p,n,&syg);    }
          



        t2=clock();
        printf("oi sygriseis poy eginan einai : %.0f\n",fabs(syg));
        printf("xronos poy xreiastike :%d microsecond\n",(t2));
                
       /*for(i=0;i<MAX;i++)
        {
                printf("stoixeia pinaka %d\n",*(p+i));
        }	*/
           
}