归并排序递归版的核心逻辑是分治：先二分至子数组长度≤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 实现
#include#include void merge(std::vector
& arr, int l, int m, int r) { std::vector temp(r - l + 1); // 临时空间，大小必须是子数组总长 int i = l, j = m + 1, k = 0; while (i zuojiankuohaophpcn= m && j zuojiankuohaophpcn= r) { if (arr[i] zuojiankuohaophpcn= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i zuojiankuohaophpcn= m) temp[k++] = arr[i++]; while (j zuojiankuohaophpcn= r) temp[k++] = arr[j++]; // 必须拷回原位置：从 arr[l] 开始，共 temp.size() 个元素 std::copy(temp.begin(), temp.end(), arr.begin() + l);}
void mergeSort(std::vector
& arr, int l, int r) { if (l // 使用示例： // std::vector
v = {38, 27, 43, 3, 9, 82, 10}; // mergeSort(v, 0, v.size() - 1); 为什么不能用
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)，这点常被忽略——如果内存受限，得考虑迭代版或原地归并（后者实现复杂且不稳定）。
