C++实现归并排序算法 _ 分治法思想与合并逻辑【详解】

归并排序必须用额外空间，因为合并时需同时读取两个子数组并写入新序列，原地操作会覆盖未读数据；临时缓冲区是算法正确性前提，非可选优化。

归并排序为什么必须用额外空间

这几乎是归并排序最核心的特性，也是新手最容易“头铁”去挑战的地方。道理很简单：合并过程需要同时“盯着”两个已经排好序的子数组，然后按顺序挑选元素，写入一个新的有序序列。如果试图在原数组上直接“挪动”元素，必然会覆盖掉那些还没来得及读取的数据，导致排序结果彻底错乱。

所以，那个用std::vector或者new int[n]分配的临时缓冲区，可不是什么性能优化选项，而是算法正确性的“铁律”。很多人不信邪，尝试在原数组上做“交错覆盖”，结果往往在mid（中点）附近出现数据混乱或者重复拷贝。

典型的翻车现场什么样？你的merge函数跑完，结果顺序不对；或者处理一个简单数组{3,1}，排序后竟然变成了{1,1}或{3,3}——这十有八九就是没用独立的temp数组，或者拷贝回原数组时边界算错了。

几个实操建议，能帮你避开这个坑：

• 临时数组随用随建：每次进入递归调用，老老实实分配一个大小为r - l + 1的临时数组。别想着复用全局缓冲区，那在多线程或嵌套调用时就是灾难。
• 拷贝回原数组要带偏移：合并完成后，用std::copy或者循环把temp里的数据拷回arr[l..r]这个区间。别忘了加上+l这个偏移量，否则全拷到数组开头去了。
• 善用局部对象管理生命周期：如果用std::vector，强烈建议在mergeSort函数内部局部声明。这样出了作用域自动释放，省心又安全，避免了手动管理内存的失误。

递归边界和区间划分的常见越界

归并排序的分治逻辑，极度依赖区间定义的一致性。你是用闭区间[l, r]，还是左闭右开[l, r)？一旦混用，mid的计算、子数组的长度、递归终止条件全都会乱套。

这里有个常见的错误模式：计算中点时写了int mid = (l + r) / 2，然后递归调用时传mergeSort(arr, l, mid-1)和mergeSort(arr, mid+1, r)。这么写，mid位置的那个元素直接被“踢出”了排序队列，而且当l == r时，mid-1很可能小于l，直接导致无限递归或者数组访问越界。

怎么处理才稳妥？

• 选定一种区间约定，并贯彻始终：如果统一用闭区间[l, r]，那么中点计算应该是mid = l + (r - l) / 2（防溢出写法），对应的递归调用是mergeSort(arr, l, mid)和mergeSort(arr, mid+1, r)。
• 终止条件要严谨：必须是if (l >= r) return;。写成if (l == r)是不够的，因为空区间（l > r）的情况可能被传入，需要这个条件来拦截。
• 测试用例要覆盖边界：至少用空数组（size = 0）、单元素数组（size = 1）和双元素数组（size = 2）跑一遍，看看程序会不会崩溃或者输出奇怪的结果。

立即学习“C++免费学习笔记（深入）”；

合并逻辑里指针移动和边界判断的顺序不能颠倒

merge函数是整个排序的“发动机”，本质上是三指针操作：i指向左子数组，j指向右子数组，k指向临时数组。这里最微妙的陷阱在于指针移动和边界判断的顺序。

看看这段看似正确但暗藏风险的代码：

if (left[i] <= right[j]) {
    temp[k++] = left[i++];
} else {
    temp[k++] = right[j++];
}

问题在哪？它假设了left[i]和right[j]永远有效。一旦i已经走到了left数组的末尾，而j还没走完，下一次循环再访问left[i]就是越界行为，程序可能崩溃或读取到垃圾数据。

正确的写法应该像这样，把边界判断放在前面：

• 主循环只处理“两边都还有货”的情况：用一个while循环，条件设为i < left_len && j < right_len，确保每次比较时指针都是有效的。
• 用独立的循环处理“收尾”工作：主循环结束后，左子数组或右子数组可能还有剩余元素。这时候需要用两个独立的while循环，分别将剩余部分直接拷贝到临时数组末尾。
• 长度计算要精确：如果手写数组版本（不用vector），务必用len_left = mid - l + 1来计算左子数组的真实长度，别想当然地写成mid - l。

STL容器与原始数组传参的陷阱

使用C++的STL容器固然方便，但传参方式不对，照样掉坑里。比如，函数签名如果写成void mergeSort(std::vector arr)（值传递），那么递归过程中修改的只是这个向量的副本，外面的原数组纹丝不动，排序了个寂寞。

另一种情况是使用原始指针int* arr，却忘了把子数组的长度或边界信息传递下去，导致merge函数里根本不知道左右子数组到哪里结束。

从性能角度看，在递归深层连续调用vector::data()获取底层裸指针进行操作，通常比反复使用operator[]要快一些。但如果你用的是std::array或者栈上的原生数组，可得留神它们的生命周期，必须确保在整个递归调用链结束前都有效。

几个实用的建议：

• 统一使用引用传参：排序函数的签名建议固定为void mergeSort(std::vector& arr, int l, int r)，这样既能修改原数组，又避免了不必要的拷贝开销。
• 提前计算迭代器，避免重复开销：如果封装成类成员函数，或者在merge函数里频繁计算子数组起点，可以提前存一下：auto left_begin = arr.begin() + l，效率更高。
• 善用断言辅助调试：在merge函数的开头加上断言，例如assert(l <= mid && mid < r)，可以在区间计算错误时立刻暴露问题，快速定位。

说到底，归并排序的难点不在于理解其分治思想，而在于让l（左边界）、r（右边界）、mid（中点）、temp（临时数组）这四个关键变量，在每一层递归中都保持逻辑自洽。尤其是当你尝试加入优化（比如对小数组改用插入排序），或者将其改写成迭代版本时，边界的偏移和内存的拷贝点会变得异常敏感，任何一个细节的疏忽都可能导致前功尽弃。