代码

#include <algorithm>

void mergeSortHelper(unsigned *a, int left, int right, unsigned *temp) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    
    // 递归划分左右两半
    mergeSortHelper(a, left, mid, temp);
    mergeSortHelper(a, mid + 1, right, temp);
    
    // 合并两个有序子数组
    int i = left;
    int j = mid + 1;
    int k = left;
    
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    
    // 处理剩余元素
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    while (j <= right) {
        temp[k++] = a[j++];
    }
    
    // 将合并后的结果拷贝回原数组
    for (int p = left; p <= right; ++p) {
        a[p] = temp[p];
    }
}

void sort(unsigned *a, int n) {
    if (n <= 1) return;
    
    // 动态分配一次辅助数组，避免在递归中频繁开辟内存
    unsigned *temp = new unsigned[n];
    
    mergeSortHelper(a, 0, n - 1, temp);
    
    // 释放内存，防止内存泄漏
    delete[] temp;
}

评测结果