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）可能出现在某些边界调用中，也该直接返回。
立即学习“C++免费学习笔记（深入）”；
区间中点计算推荐用 mid = left + (right - left) / 2，避免 left + right 溢出（尤其在索引很大时）。不要用 (left + right) >> 1，虽然等价但可读性差，且编译器优化足够好，没必要手动位运算。
递归调用顺序必须是：先排左半，再排右半，最后合并。顺序颠倒会导致合并时数据未就绪。
原地 merge 是否可行？为什么一般不这么做
理论上存在原地归并算法（如使用旋转操作），但时间复杂度退化为 O(n²) 或常数因子极大，实际工程中几乎不用。标准归并排序的空间复杂度是 O(n)，这是合理代价。
常见误区：
- 试图复用原数组做临时空间——会覆盖未处理的数据
- 在递归过程中反复 new/delete 数组——导致频繁内存分配，性能暴跌
- 用 vector 的
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 又有构造开销。最稳妥的是在顶层函数申请一次，作为参数传入递归函数。
