代码

#include <algorithm>
const int N=1e8;
unsigned T[N];
void merge_sort(unsigned *A,int x,int y,unsigned *T) // 从x到y排序（左闭右开）
{
    if(y-x>1){
        int m=x+(y-x)/2; // 划分
        int p=x,q=m,i=x;
        merge_sort(A,x,m,T); // 递归求解
        merge_sort(A,m,y,T);
        while(p<m||q<y){ // p和q相当于两个指针
            if(q>=y||(p<m&&A[p]<=A[q])) // 加入左半数组的两种情况
                T[i++]=A[p++]; 
            else T[i++]=A[q++];
        }
        for(i=x;i<y;i++)A[i]=T[i]; // 从辅助空间复制回A数组
    }
}
void sort(unsigned *a, int n) {
	merge_sort(a, 0, n,T);
}

评测结果