重开（acwing）：归并排序

//先递归 再排序 再归并
#include<iostream>
using namespace std;
const int N=10010;
int n,a[N],tm[N]; //tm是临时数组存当时函数里的排序
void merge_sort(int l,int r,int a[])
{
    if(l>=r)
        return;
    int mid=l+r>>1;      //分成两段
    merge_sort(l,mid,a);    //先递归
    merge_sort(mid+1,r,a);
    int i=l,j=mid+1,k=0;           //i是第一段，从l到mid；j是第二段，从mid+1到r
    while(i<=mid&&j<=r)           
        if(a[i]<a[j])             //两段都从左到右比较，哪个小就存入临时数组
            tm[k++]=a[i++];
    else
        tm[k++]=a[j++];
    while(i<=mid)tm[k++]=a[i++];      //将第一段或者第二段可能还剩下的数存进去
    while(j<=r)tm[k++]=a[j++];
    for(i=l,j=0;i<=r;i++,j++)            //将临时数组里的存回a中 
        a[i]=tm[j];
}

int main(void)
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    merge_sort(1,n,a);
    for(int i=1;i<=n;i++)
        cout<<a[i]<<' ';
    cout<<endl;
    return 0;
}