c++中如何实现归并排序_c++分治思想归并排序算法【详解】_技术教程

归并排序的核心是分治三步：split切分、merge合并、combine写回；merge需用临时数组、半开区间、正确边界控制，且应复用辅助空间而非重复分配。

归并排序的核心逻辑是分治，不是递归本身

归并排序的正确理解起点不是“写个递归函数”，而是明确三步：split（切分到单元素）、merge（合并两个有序段）、combine（把合并结果写回原数组）。递归只是实现 split 的自然手段，但容易让人忽略 merge 的边界控制——这才是实际编码出错最多的地方。

切分时用 [left, right) 半开区间比 [left, right] 更少出错，避免 mid = (left + right) / 2 溢出可改用 mid = left + (right - left) / 2
merge 必须用临时数组暂存结果，不能边合并边写回原数组，否则会覆盖未读取的数据
合并循环的终止条件不是“两个子数组都空”，而是“至少一个已耗尽”，剩余部分直接拷贝

标准实现中 `merge` 函数的四个关键参数

很多初学者把 merge 写成只接受两个独立数组的函数，这在归并排序里反而增加复杂度。实际应传入原数组指针 + 三段下标：arr、left、mid、right（mid 是左半段末尾+1，即右半段起始位置）。

left 到 mid-1 是左有序段
mid 到 right-1 是右有序段
合并结果要填回 arr[left] 到 arr[right-1]
临时数组大小必须是 right - left，而非固定长度或 arr.size()

避免内存重复分配的常见优化

每次递归都 new 临时数组会导致大量堆分配，尤其对大数组性能敏感。更合理的方式是在顶层调用时一次性分配好辅助空间，全程复用。

void mergeSort(vector& arr) {
    if (arr.size() <= 1) return;
    vector temp(arr.size()); // 一次分配
    mergeSortHelper(arr, temp, 0, arr.size());
}
void mergeSortHelper(vector& arr, vector& temp, int left, int right) {
if (right - left <= 1) return;
int mid = left + (right - left) / 2;
mergeSortHelper(arr, temp, left, mid);
mergeSortHelper(arr, temp, mid, right);
merge(arr, temp, left, mid, right);
}