C++模板
using namespace std;
void mergesort(int *,int,int);
void merge(int *,int,int,int);
int main()
{
int n;
cin>>n;
int *arr=new int[n];
for(int i=0;i<n;i++)
cin>>arr[i];
mergesort(arr,0,n-1);
for(int i=0;i<n;i++)
cout<<arr[i]<<' ';
delete[] arr;
return 0;
}
void mergesort(int *arr,int l,int r)
{
if(l>=r)
return;
int middle=(l+r)/2;
mergesort(arr,l,middle);
mergesort(arr,middle+1,r);
merge(arr,l,middle,r);
return;
}
void merge(int *arr,int l,int middle,int r)
{
int *teparr=new int[r-l+1];
int i=l,j=middle+1,cnt=0;
while(i<=middle&&j<=r)
{
if(arr[i]<arr[j])
teparr[cnt++]=arr[i++];
else
teparr[cnt++]=arr[j++];
}
while(i<=middle)
teparr[cnt++]=arr[i++];
while(j<=r)
teparr[cnt++]=arr[j++];
for(int i=0;i<cnt;i++)
arr[l+i]=teparr[i];
delete[] teparr;
return;
}