归并排序核心是分治与辅助数组合并，C++中需显式管理临时空间；关键在精准控制left、mid、right边界，用temp安全合并，避免越界或覆盖；merge函数须严格按两段已排序子数组处理，双指针分别从left和mid+1开始。
归并排序的核心是分治 + 辅助数组合并
归并排序在 C++ 中必须显式管理辅助空间，不能像 Python 那样靠切片隐式分配。关键不是“写个递归”，而是控制好 left、mid、right 三段边界，以及用临时数组 temp 安全合并——否则极易越界或覆盖原数组。
merge 函数怎么写才不出错
常见错误是下标计算混乱，比如把 mid + 1 写成 mid，或漏掉 right - left + 1 的长度判断。合并逻辑必须严格按两段已排序子数组处理：
- 两个指针分别从
left和mid + 1开始扫描 - 比较时用
arr[i] （注意等号，保证稳定） - 复制剩余元素时，只复制未完的一段，不能无脑循环到
right - 最后必须把
temp中[0, right-left]范围拷回arr[left]起始位置
void merge(std::vector& arr, int left, int mid, int right) { std::vector temp(right - left + 1); int i = left, j = mid + 1, k = 0; while (i zuojiankuohaophpcn= mid && j zuojiankuohaophpcn= right) { if (arr[i] zuojiankuohaophpcn= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while (i zuojiankuohaophpcn= mid) temp[k++] = arr[i++]; while (j zuojiankuohaophpcn= right) temp[k++] = arr[j++]; for (int idx = 0; idx zuojiankuohaophpcn temp.size(); ++idx) { arr[left + idx] = temp[idx]; }}
mergesort 递归调用的边界条件怎么设
递归终止条件必须是
left >= right，而不是left == right——否则当输入为空或单元素时可能跳过，尤其用vector时size()==0会导致left=0, right=-1，此时left > right才合法。调用时传入的是闭区间[left, right]，所以拆分是：
- 左半：
left到mid（含）- 右半：
mid + 1到right（含）mid计算用(left + right) / 2，整数除法向下取整，安全void mergesort(std::vector
& arr, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; mergesort(arr, left, mid); mergesort(arr, mid + 1, right); merge(arr, left, mid, right); } 为什么不能直接在原地合并
归并排序本质需要同时读取两段有序数据、写入第三段空间。如果试图在原数组上“边读边写”，会覆盖尚未读取的元素——例如左段最大值还没被取走，就被右段较小值提前写入左段位置。这也是所有标准实现都依赖额外
O(n)空间的根本原因。用std::inplace_merge是特例，它底层仍需临时缓冲，且仅适用于已分割好的连续迭代器范围，不适用于通用递归分治场景。最容易被忽略的是：每次
merge前，左右两段必须各自有序——这个前提由递归保证，但调试时若发现结果错乱，第一反应不该是改merge，而应检查递归是否真把[left, mid]和[mid+1, right]分对了，尤其是mid的计算和传递有没有溢出或截断。
or
