为什么我实现的C/C++归并排序（merge sort）远慢于网上参考代码？

核心问题原因 #

• 临时数组分配尺寸过大：你的merge函数中每次都申请h+1长度的数组，h是整个数组的最高下标。以20万条数据为例，无论当前合并的子数组有多小（比如仅合并2个元素），你都会申请长度为20万的数组，不仅内存分配开销指数级上升，还会带来大量不必要的缓存失效问题。参考代码仅申请当前待合并的两个子数组总长度的内存，底层递归时内存开销仅为你的几万分之一。
• 多余的数组初始化：你申请数组时加了()语法，会将数组所有元素初始化为0，而这些元素后续都会被排序结果覆盖，初始化操作完全多余，增加了额外耗时。参考代码没有做这步无意义的初始化。

修复后的merge代码示例 #

void merge(int *arr, int l, int mid, int h) {
    int i = l, j = mid+1, k = 0;
    // 仅申请当前待合并区间的长度，不需要分配整个数组大小，也不需要初始化
    int len = h - l + 1;
    int* newSorted = new int[len];
    while (i <= mid && j <= h) {
        if (arr[i] < arr[j])
            newSorted[k++] = arr[i++];
        else
            newSorted[k++] = arr[j++];
    }
    for (; i <= mid; i++)
        newSorted[k++] = arr[i];
    for (; j <= h; j++)
        newSorted[k++] = arr[j];
    // 拷贝回原数组，注意临时数组下标从0开始
    for (int x = 0; x < len; x++)
        arr[l + x] = newSorted[x];
    delete[] newSorted;
}

修改后耗时会和参考代码基本持平。

额外优化建议 #

可以在进入mergeSort前提前申请一个和原数组等长的临时数组，整个排序过程复用该临时数组，完全避免递归过程中频繁的new/delete堆内存分配释放开销，性能会比参考代码更高。

内容的提问来源于stack exchange，提问作者BhuvansaiP