归并和快排类似，都是分治，都是把问题分为子问题解决后合并。

#include<iostream>
using namespace std;
const int N=10010;
int n,q[N];
int t[N];//用于存储
void merge_sort(int q[],int l,int r)
{
    if(l>=r)return;

    //第一步：将问题分成子问题：均分左右俩边
    int mid=l+r>>1;

    //第二步：处理子问题
    merge_sort(q,l,mid),merge_sort(q,mid+1,r);

    //第三步：合并子问题
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(q[i]<=q[j])t[k++]=q[i++];
        else t[k++]=q[j++];
    }
    //填充剩余部分
    while(i<=mid)t[k++]=q[i++];
    while(j<=r)t[k++]=q[j++];

    //将存储数组复制回原数组
    for(int i=0,j=l;j<=r;i++,j++)q[j]=t[i];


}


int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>q[i];
    }
    merge_sort(q,0,n-1);
    for(int i=0;i<n;i++)
    {
        cout<<q[i]<<' ';
    }
}