归并排序递归版的核心逻辑是分治：先二分至子数组长度≤1，再合并已排序子数组；关键在merge过程，需用临时数组避免覆盖，三指针合并后拷回原数组。
归并排序递归版的核心逻辑是什么
归并排序递归版本质是「分治」：把数组不断二分直到子数组长度 ≤ 1（自然有序），再逐层合并两个已排序的子数组。关键不在“递归调用”，而在 merge 过程——它必须用额外空间暂存结果，否则原地合并会覆盖未读取的数据。
如何正确写 merge 函数避免越界和覆盖
常见错误是直接往原数组 arr 写入，却没备份左/右半段；或下标计算错导致访问 arr[mid+1] 越界。必须用临时数组保存合并结果，再整体拷回。
-
left子数组范围是[l, m]（闭区间），right是[m+1, r] - 三指针：i 指向左段起始，j 指向右段起始，k 指向临时数组起始
- 合并完后，用
std::copy或循环把temp中[0, r-l+1)段拷回arr[l]开始的位置
c++ 递归归并排序完整可运行代码
以下代码通过 vector<int></int> 实现，避免手动管理内存，同时标注了易错点：
#include <vector>
#include <algorithm>
<p>void merge(std::vector<int>& arr, int l, int m, int r) {
std::vector<int> temp(r - l + 1); // 临时空间，大小必须是子数组总长
int i = l, j = m + 1, k = 0;</p><pre class='brush:php;toolbar:false;'>while (i <= m && j <= r) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= m) temp[k++] = arr[i++];
while (j <= r) temp[k++] = arr[j++];
// 必须拷回原位置：从 arr[l] 开始，共 temp.size() 个元素
std::copy(temp.begin(), temp.end(), arr.begin() + l);}
立即学习“C++免费学习笔记（深入）”；
void mergeSort(std::vector // 使用示例：
// std::vector 函数参数写 另外，递归深度是 为什么不能用
int arr[] 直接传参void mergeSort(int arr[], int l, int r) 看似简洁，但实际是 int*，无法获取数组长度，r 完全依赖调用方传入——一旦错传（比如把 sizeof(arr)/sizeof(*arr) 写在函数内），就会越界。用 std::vector 或传入迭代器范围（如 begin, end）更安全、更现代。O(log n)，但每层 merge 都要分配临时空间，总空间复杂度是 O(n)，这点常被忽略——如果内存受限，得考虑迭代版或原地归并（后者实现复杂且不稳定）。
