#include "stdio.h"
#include "malloc.h"
int times=0;

void Merge(int data1[],int data2[],int s,int m,int n){
	int i,j,k;
	for(i=m+1,k=s;s<=m&&i<=n;++k)
		if(data1[s]<data1[i])data2[k]=data1[s++];
		else data2[k]=data1[i++];
	for(j=s;j<=m;++j,++k)
		data2[k]=data1[j];
	for(j=i;j<=n;++j,++k)
		data2[k]=data1[j];
}

void Msort(int data1[],int data2[],int n,int len){
	int start_p,end_p;
	start_p=0;
	while(start_p+len<n){
		end_p=start_p+2*len-1;
		if (end_p>=n)end_p=n-1;
		Merge(data1,data2,start_p,start_p+len-1,end_p);

		start_p=end_p+1;
	}
	if(start_p<n)
		for(;start_p<n;start_p++)data2[start_p]=data1[start_p];
}

void mergesort(int data1[],int n){
	int length=1,k=0;
	int *data2;
	data2=(int *)malloc(sizeof(int)*n);
	if(data2==NULL)return;

	while(length<n){
		if(k==0)Msort(data1,data2,n,length);
		else Msort(data2,data1,n,length);
		times++;
		length*=2;
		k=1-k;
	}
	if(k==1)
		for(k=0;k<n;++k)data1[k]=data2[k];
}




void main()
{
	int i;
	int list[9];
	for (i=0;i<10;i++)
	{
		printf("Input num %d:",i);
		scanf("%d",&list[i]);
	}

	printf("\nThe list is:");
	for(i=0;i<10;i++)printf("%d ",list[i]);

	mergesort(list,10);

	printf("\nThe sorted list is:");
	for(i=0;i<10;i++)printf("%d ",list[i]);
	printf("\nThe merge times is:%d",times);

}