merge函数需确保左右子区间闭区间为[left, mid]和[mid+1, right]，用i、j双指针遍历，任一越界后须补全另一侧剩余元素，临时数组大小为right−left+1。

merge 函数怎么写才不越界

标准库 std::merge 要求左右两个子区间都已排序，且目标空间足够大。自己手写时最容易出错的是边界判断——比如把 mid 算错导致左半段多拷一个、右半段少拷一个，或者在合并循环里没处理某一边耗尽后的剩余元素。

关键点：

• 左区间是 [left, mid]，右区间是 [mid + 1, right]（闭区间），别写成 [left, mid) 混淆
• 合并时用两个指针 i 和 j 分别遍历左右段，每次取较小值；任一指针越界后，必须把另一侧剩余全部拷过去
• 临时数组大小必须是 right - left + 1，不能只开 right - left

示例片段（核心合并逻辑）：

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++];

递归分治的终止条件和区间划分

归并排序递归到底的条件不是 size == 1，而是 left >= right——因为单个元素（left == right）不需要再分，而空区间（left > right）可能出现在某些边界调用中，也该直接返回。

区间中点计算推荐用 mid = left + (right - left) / 2，避免 left + right 溢出（尤其在索引很大时）。不要用 (left + right) >> 1，虽然等价但可读性差，且编译器优化足够好，没必要手动位运算。

递归调用顺序必须是：先排左半，再排右半，最后合并。顺序颠倒会导致合并时数据未就绪。

原地 merge 是否可行？为什么一般不这么做

理论上存在原地归并算法（如使用旋转操作），但时间复杂度退化为 O(n²) 或常数因子极大，实际工程中几乎不用。标准归并排序的空间复杂度是 O(n)，这是合理代价。

常见误区：

• 试图复用原数组做临时空间——会覆盖未处理的数据
• 在递归过程中反复 new/delete 数组——导致频繁内存分配，性能暴跌
• 用 vec

  

  tor 的 insert 或 erase 实现合并——每次操作都是 O(n)，整体变慢

正确做法：一次性分配一个辅助数组（或 vector），在所有递归层共用，通过传引用或全局缓存避免重复分配。

STL 中 stable_sort 是不是归并排序

在 libstdc++（GCC）和 libc++（Clang）中，std::stable_sort 底层确实是基于归并排序的优化变种（如混合了插入排序的小数组优化、内存池管理、自底向上非递归实现等）。但它不保证一定是“教科书式”的递归分治归并——比如当可用内存不足时，可能退化为 heap sort 以保证 O(n log n) 最坏性能。

所以：

• 如果你需要稳定排序且不关心具体算法，直接用 std::stable_sort 更可靠
• 如果是为了理解分治思想、调试中间状态、或嵌入到特定内存受限环境，才值得手写归并
• std::sort 不稳定，且底层通常是 introsort（快排+堆排+插排混合），不满足稳定性要求

真正容易被忽略的是：手写归并时，temp 数组的生命周期管理——局部栈数组太小，new 后忘了 delete 会泄漏，用 vector 又有构造开销。最稳妥的是在顶层函数申请一次，作为参数传入递归函数。