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


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=*(r1++);
                 			 }
         			             else if(a2<p+n)
                                     	             {
            				                (*syg)+=4;
     				                *r3=*(a2++);
     			             }
            			            else
               		            {
                    				 (*syg)+=4;
               				  break;
          			            }

        		     }


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


       free(a);

       return 1;
      }

   }

 return 1;

}






int main()

 {
        int *p;
        int n=MAX;
        long double syg=0;
        clock_t t2;
	
	p=(int *)malloc(MAX+100000000);
        
	

        for(i=0;i<MAX;i++)
         {
              printf("dose stoixeio toy pinaka\n");
	scanf("%d",p+i);
         }
                
         
         
        for(i=0;i<MAX;i++)
        {
                printf("stoixeia pinaka %d\n",*(p+i));

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