归并排序

思想：分治（从下而上）

void process(int arr[],int L,int mid,int R)
{
	int* a=(int*)malloc(sizeof(int)*(R-L+1);
	int i=L;
	int j=mid+1;
	int k=0;
	while(i<=mid&&j<=R)
	{
		if(arr[i]<arr[j])
			a[k++]=arr[i++];
		else a[k++]=arr[j++];
	}
	while(i<=mid)
		a[k++]=arr[i++];
	
	while(j<=R)
		a[k++]=arr[j++];
	
	int n=0;
	for(;n<k;++n)
		arr[L++]=a[n];
}

void mergesort(int arr[],int L,int R)
{
	if(L==R)
		return ;
	int mid=L+((R-L)>>1);
	mergesort(arr,L,mid);
	mergesort(arr,mid+1,R);
	process(arr,L,mid,R);
}