C++ 代码

#include<iostream>

using namespace std;
const int N = 1e6 + 10;
int a[N], p[N];
int n;

void merge_sort(int a[], int l, int r)
{
    if(l>=r)
        return ;
    int mid = (l+r) >> 1;
    merge_sort(a, l, mid), merge_sort(a, mid+1, r);

    int k=0, i = l, j = mid+1;
    while(i<=mid && j<=r)   // 利用2个数组进行排序
        if(a[i] <= a[j])
            p[k++] = a[i++];
        else
            p[k++] = a[j++];
    while(i<=mid)   // 左集合剩余节点
        p[k++] = a[i++];
    while(j<=r)   // 右集合剩余节点
        p[k++] = a[j++];
    for(i=l, j=0; i<=r; i++, j++)   // 子集合局部合并
        a[i] = p[j];
}

// 确定分界点：mid=(l+r)/2
// 递归排序left，right
// 归并——合二为一
int main()
{
    cin >> n;
    for(int i=0; i<n; i++)
        scanf("%d", &a[i]);
    merge_sort(a, 0, n-1);

    for(int i=0; i<n; i++)
        printf("%d ", a[i]);

    return 0;
}