归并排序核心是分治与辅助数组合并，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<int>& arr, int left, int mid, int right) {
std::vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
<pre class='brush:php;toolbar:false;'>while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) temp[k++] = arr[i++];
else temp[k++] = arr[j++];
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];
for (int idx = 0; idx < temp.size(); ++idx) {
arr[left + idx] = temp[idx];
}}
mergesort 递归调用的边界条件怎么设
递归终止条件必须是 left >= right，而不是 left == right——否则当输入为空或单元素时可能跳过，尤其用 vector 时 size()==0 会导致 left=0, right=-1，此时 left > right 才合法。调用时传入的是闭区间 [left, right]，所以拆分是：
立即学习“C++免费学习笔记（深入）”；
- 左半：
left到mid（含） - 右半：
mid + 1到right（含） -
mid计算用(left + right) / 2，整数除法向下取整，安全
void mergesort(std::vector<int>& 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 的计算和传递有没有溢出或截断。
