归并排序模板

#include<iostream>
using namespace std;

const int N = 100010;
int n;
int q[N], w[N];

void merge_sort(int l, int r){
    if(l>=r)    return ;
    int mid = (l + r)>>1; //归并排序先确定分界点

    merge_sort(l, mid), merge_sort(mid+1, r);   //左右分别递归排序

    int k=0,i=l,j=mid+1;                        //归并
    while(i<=mid && j <=r){
        if(q[i]< q[j]) w[k++]=q[i++];   //这里比较的是原数组,而不是待拷贝的数组
        else w[k++] = q[j++];
    }

    while(i<=mid)   w[k++]=q[i++];
    while(j<=r) w[k++]=q[j++];

    for(int i=l,j=0;i<=r;i++,j++)   q[i]=w[j];
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++)    cin>>q[i];
    merge_sort(0, n-1);

    for(int i=0;i<n;i++)    cout<<q[i]<<" ";

    return 0;
}