归并排序核心是递归拆分与有序合并：先二分至单元素，再双指针合并；merge需用临时数组避免覆盖，下标边界和终止条件必须严谨。
归并排序的核心逻辑是递归拆分 + 有序合并
它不靠交换元素位置来排序，而是把数组不断二分到单个元素，再把已排好序的子数组逐层合并。关键在 merge 这一步——必须用额外空间暂存结果，否则原地合并会覆盖未读取的数据。
常见错误是写成“边比较边往原数组写”，导致左半段还没读完就被右半段的值覆盖。正确做法是先复制左右两段到临时缓冲区，再双指针归并回原数组。
- 递归终止条件必须是
left >= right（单个元素或空区间），不能写成left == right，否则长度为 0 的区间会无限递归 -
mid要用(left + right) / 2或更安全的left + (right - left) / 2，避免整数溢出 - 合并时临时数组大小应为
right - left + 1，别少算 1
标准 C++ 实现中 merge 函数怎么写才不出错
手写 merge 是最容易翻车的地方：下标越界、漏拷贝、边界判断反了都会让结果乱序或崩溃。
典型场景是合并 arr[left...mid] 和 arr[mid+1...right] 这两个闭区间子数组：
立即学习“C++免费学习笔记（深入）”；
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
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 < k; ++idx) arr[left + idx] = temp[idx];
}- 注意
i 和 <code>j ，不是 <code><—— 因为传入的是闭区间 - 两个补全循环不能省，否则尾部元素会丢失
- 最后拷回原数组时，起始位置是
left，不是0
为什么不用 std::inplace_merge？它和手写有啥区别
std::inplace_merge 看似省事，但它要求输入区间已经各自有序，且合并后仍需保持原容器内存连续——对 vector 没问题，但对 list 就是真·原地；而手写归并排序里，inplace_merge 无法替代递归分治过程本身。
真正的问题在于：你没法直接拿它组装出完整归并排序，因为 inplace_merge 不负责拆分，也不控制递归深度。
- 调用它前必须确保
[first, middle)和[middle, last)都已升序，否则结果不可预测 - 它的平均时间复杂度仍是 O(n)，但常数比手写高，且内部可能分配临时缓冲区
- 如果用它写归并排序，代码反而更难调试：分治逻辑和合并逻辑被 STL 隐藏，出错时连哪一层合并失败都看不出来
递归太深导致栈溢出？改迭代版要注意什么
对百万级数组，纯递归可能触发栈溢出（尤其 Windows 默认栈仅 1MB）。迭代版用队列或栈模拟递归过程，但容易忽略合并顺序——必须从小到大合并子数组，否则 merge 时左右区间不满足有序前提。
正确做法是按子数组长度分层处理：len = 1, 2, 4, ...，每次合并所有长度为 len 的相邻区间。
- 外层循环变量是
len，不是索引；内层遍历步长是2 * len - 每次合并的右边界要取
min(left + 2 * len - 1, n - 1)，防止越界 - 中间点
mid是left + len - 1，不是(left + right) / 2
真正麻烦的不是写法，而是调试时得同时盯住三层变量：当前 len、每个 left、以及 merge 内部的指针——稍一疏忽，某个子区间就漏合并了。
