猫史档案馆

rt

code：

 

#include<iostream>
using namespace std;
void Merge(int *a,int l,int mid,int r,int length);
void MergeSort(int *a,int l,int r)
{
	if(l>=r)
		return;
	int mid=l+(r-l)>>1;
	MergeSort(a,l,mid);//sort left
	MergeSort(a,mid+1,r);//sort right
	Merge(a,l,mid,r,r-l+1);//Merge
}
void Merge(int *a,int l,int mid,int r,int length)
{
	int help[length];
	int i=0,p1=l,p2=mid+1;
	while(p1<=mid && p2<=mid)
		help[i++]=a[p1]<=a[p2]?a[p1++]:a[p2++];
	while(p1<=mid)
		help[i++]=a[p1++];
	while(p2<=r)
		help[i++]=a[p2++];
	for(i=0;i<length;i++)
		a[l+i]=help[i];
	
}
int main()
{
	int n;//n is the length of arr.
	cin>>n;
	int arr[n];
	for(int i=0;i<n;i++)//input arr
	{
		cin>>arr[i];
	}
	MergeSort(arr,0,n-1);
	for(int i=0;i<n;i++)//output arr
	{
		cout<<arr[i]<<" ";
	}
	return 0;
}

return 0;
}