#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define max 30000
int ar[max+1];
int sub[max+1];
int fg;
void ins(int low,int high)
{
	int i,j;
	for(j=low+1;j<=high;j++)
	{
		int t=ar[j];
		i=j-1;
		while(i>=low && ar[i]>t)
		{
			ar[i+1]=ar[i];
			i--;
		}
		ar[i+1]=t;
	}

}
void merge(int low,int mid,int high)
{
	int i=low;

	int j=mid+1;
	int k=0,l;
	while(i<=mid && j<=high)
	{
		if(ar[i]<ar[j])
			sub[k++]=ar[i++];
		else
			sub[k++]=ar[j++];

	}
	if(i>mid)
	{
		for(l=j;l<=high;l++)
			sub[k++]=ar[l];
	}
	else
		for(l=i;l<=mid;l++)
			sub[k++]=ar[l];
		k=0;
	for(l=low;l<=high;l++)
		ar[l]=sub[k++];
}

void mergesort(int low,int high)
{
	if(fg)
	{
		if(low+15<high)
		{
			ins(low,high);

		}
		else if(low<high)
		{
			int mid=(low+high)/2;
			mergesort(low,mid);
			mergesort(mid+1,high);
			merge(low,mid,high);
		}
		else return;

	}
	else if(low<high)
	{
		int mid=(low+high)/2;
		mergesort(low,mid);
		mergesort(mid+1,high);
		merge(low,mid,high);
	}
	else return;
}
int main()
{
	int i;
	FILE *fp;
	fp=fopen("input.txt","w");
	for(i=1;i<=max;i++)
	{
		fprintf(fp,"%d ",rand()%10000);
		if(i%10==0)
			fprintf(fp,"%c",10);
	}
	fclose(fp);
	fp=fopen("input.txt","r");
	 i=0;
	while(fscanf(fp,"%d",&ar[i++])!=-1);
	fclose(fp);
	clock_t cal,en;
	cal=clock();

	mergesort(0,max-1);

	en=clock();

	double div=CLOCKS_PER_SEC;

	double t=(en-cal)/div;


	printf("%lf\n",t);
	fp=fopen("output.txt","w");

	for(i=0;i<max;i++)
	{
		fprintf(fp,"%d ",ar[i]);
		if((i+1)%10==0)
			fprintf(fp,"\n");
	}

	fprintf(fp,"total time %lf sec\n\n",t);
	fclose(fp);

	fp=fopen("input.txt","r");
	 i=0;
	while(fscanf(fp,"%d",&ar[i++])!=-1);
	fclose(fp);
		fp=fopen("output.txt","a");
	cal=clock();
	fg=1;
	mergesort(0,max-1);

	en=clock();

	div=CLOCKS_PER_SEC;

	t=(en-cal)/div;
		for(i=0;i<max;i++)
	{
		fprintf(fp,"%d ",ar[i]);
		if((i+1)%10==0)
			fprintf(fp,"\n");
	}

	fprintf(fp,"total time %lf sec\n\n",t);
		printf("%lf\n",t);
	fclose(fp);



	return 0;
}