#include <math.h>#include <stdio.h>#include <time.h>#include <stdlib.h>#define INFINITY 2147483647double insertion_sort(unsigned int n,unsigned int array[]);double merge_sort(unsigned int n, unsigned int array[]);void rand_order(unsigned int n,unsigned int *randArray);void asc_order(unsigned int n,unsigned int *ascArray);void des_order(unsigned int n,unsigned int *desArray);void merge(unsigned int A1[],unsigned int A2[],unsigned int m1,unsigned int m2);main(){	unsigned int n;//the size of input array	double time;//running time for n	FILE *fp_asc_inser, *fp_des_inser, *fp_rand_inser,*fp_asc_merge, *fp_des_merge, *fp_rand_merge;	int i,k;//insertion_sort	/*fp_asc_inser=fopen("asc_insertion4.txt","w+");	for(i=1;i<21;i++)	{		n=i*2500000;		unsigned int *array=malloc(sizeof(unsigned int)*n);		asc_order(n, array);		time=insertion_sort(n, array);			free(array);			fprintf(fp_asc_inser,"%-20f %-10u %-20f\n",time,n,(double)n*log((double)n)/log(2));			}	fclose(fp_asc_inser);*/	//loop k will result the slow running time	/*fp_asc_inser=fopen("asc_insertion2.txt","w+");	sumtime=0;	for(i=1;i<21;i++)	{		n=i*2500000;		for(k=0;k<4;k++)		{			unsigned int *array=malloc(sizeof(unsigned int)*n);			asc_order(n, array);			time[k]=insertion_sort(n, array);				sumtime+=time[k];			free(array);		}		avertime=sumtime/4;		fprintf(fp_asc_inser,"%-20f %-10u %-20f\n",avertime,n,(double)n*log((double)n)/log(2));			}	fclose(fp_asc_inser);*/	//fp_asc_merge=fopen("asc_merge1.txt","w+");	//for(i=1;i<2;i++)	//{			n=80000000;		unsigned int *array=malloc(sizeof(unsigned int)*n);		asc_order(n, array);		/*int k;		for(k=0;k<n;k++)		{			printf("%d\n",array[k]);		}*/		time=insertion_sort(n, array);		/*printf("the result is \n");		for(k=0;k<n;k++)		{			printf("%d\n",array[k]);		}*/			free(array);		printf("%-20f %-10u %-20f\n",time,n,(double)n*log((double)n)/log(2));			//}	//fclose(fp_asc_merge);		/*fp_rand_inser=fopen("rand_insertion.txt","w+");	sumtime=0;	printf("rand_inser begins\n");	for(i=1;i<101;i++)	{		n=i*5000;				for(k=0;k<2;k++)		{			unsigned int *array=malloc(sizeof(unsigned int)*n);			rand_order(n, array);			time1[k]=insertion_sort(n, array);				sumtime+=time1[k];			free(array);		}		avertime=sumtime/2;		fprintf(fp_rand_inser,"%-20f %-10u %-20f\n",avertime,n,(double)n*log((double)n)/log(2));			}	fclose(fp_rand_inser);//merge_sort	fp_asc_merge=fopen("asc_merge.txt","w+");	sumtime=0;	printf("asc_merge begins\n");	for(i=1;i<101;i++)	{		n=i*500000;				for(k=0;k<4;k++)		{			unsigned int *array=malloc(sizeof(unsigned int)*n);			asc_order(n, array);			time[k]=merge_sort(n, array);				sumtime+=time[k];			free(array);		}		avertime=sumtime/4;		fprintf(fp_asc_merge,"%-20f %-10u %-20f\n",avertime,n,(double)n*log((double)n)/log(2));			}	fclose(fp_asc_merge);	fp_des_merge=fopen("des_merge.txt","w+");	printf("des_merge begins\n");	sumtime=0;	for(i=1;i<101;i++)	{		n=i*500000;		for(k=0;k<4;k++)		{			unsigned int *array=malloc(sizeof(unsigned int)*n);			des_order(n, array);			time[k]=merge_sort(n, array);				sumtime+=time[k];			free(array);		}		avertime=sumtime/4;		fprintf(fp_des_merge,"%-20f %-10u %-20f\n",avertime,n,(double)n*log((double)n)/log(2));			}	fclose(fp_des_merge);		fp_rand_merge=fopen("rand_merge.txt","w+");	printf("rand_merge begins\n");	sumtime=0;	for(i=1;i<101;i++)	{		n=i*500000;				for(k=0;k<4;k++)		{			unsigned int *array=malloc(sizeof(unsigned int)*n);			rand_order(n, array);			time[k]=merge_sort(n, array);				sumtime+=time[k];			free(array);		}		avertime=sumtime/4;		fprintf(fp_rand_merge,"%-20f %-10u %-20f\n",avertime,n,(double)n*log((double)n)/log(2));	}	fclose(fp_rand_merge);*/}void rand_order(unsigned int n,unsigned int *randArray){	srandom(time(0));	unsigned int i;	for(i=0;i<n;i++)		*(randArray+i)=n*(float)random()/(float)0x7fffffff;}void asc_order(unsigned int n,unsigned int *ascArray){	unsigned int i;	for(i=0;i<n;i++)		*(ascArray+i)=i;}void des_order(unsigned int n,unsigned int *desArray){	unsigned int i;	for(i=0;i<n;i++)		*(desArray+i)=n-i;}double insertion_sort(unsigned int n,unsigned int array[]){	clock_t start,end;	double cpu_time_used;	start=clock();	int i,j,key;	for(j=1;j<n;j++)        {        	key=array[j];        	i=j-1;        	while ((i>=0) && (array[i]>key))                {                        array[i+1]=array[i];                        i--;                }        	array[i+1]=key;        }	end=clock();	cpu_time_used=((double)(end-start)/CLOCKS_PER_SEC);	return cpu_time_used;}double merge_sort(unsigned int n, unsigned int array[]){	clock_t start,end;	double cpu_time_used;	start=clock();	if(n>0)	{		int q=abs((0+n)/2);		merge_sort(q, array);		merge_sort(n-q-1, array+q+1);		merge(array,array+q+1,q,n-q-1);	}	end=clock();	cpu_time_used=((double)(end-start)/CLOCKS_PER_SEC);	return cpu_time_used;}void merge(unsigned int A1[],unsigned int A2[],unsigned int m1,unsigned int m2){		unsigned int i,j;	unsigned int B[m1+2];	unsigned int C[m2+2];	for(i=0;i<=m1;i++)		B[i]=A1[i];	for(j=0;j<=m2;j++)		C[j]=A2[j];	B[m1+1]=INFINITY;	C[m2+1]=INFINITY;	i=0;	j=0;	unsigned int m=m1+m2+2;	unsigned int k;	for(k=0;k<m;k++)	{		if(B[i]<=C[j])		{						A1[k]=B[i];			i++;		}		else		{			A1[k]=C[j];			j++;		}	}}