标准库std::merge要求输入区间已排序且目标空间足够；手写时应统一用左闭右开区间[l, mid)和[mid, r)，三路指针推进，耗尽段用std::copy补全，递归出口设为l>=r，预分配临时缓冲区避免重复分配。
merge 函数怎么写才不越界
标准库 std::merge 要求两个输入区间已排序，且目标空间足够大；手写时最容易在边界判断上出错——比如把 mid 算成开区间却用闭区间逻辑拷贝，或漏判某一段已耗尽。实际写 merge 辅助函数时，建议统一用左闭右开：[l, mid) 和 [mid, r)，这样和 std::sort 保持一致，也避免 +1/-1 混用。
常见错误现象：std::bad_alloc（目标缓冲区不够）、segmentation fault（索引越 arr[i] 的 i 超出原始数组长度）。
- 用临时
vector存合并结果，别直接往原数组里写——除非你确认写入位置不会覆盖未读数据 - 三路指针：左段游标
i、右段游标j、目标位置k，每次只推进被选中的那个 - 任一段耗尽后，用
std::copy补全另一段，别手写循环——容易漏掉++i或写错终止条件
递归分治的边界条件怎么设
归并排序的递归出口不是「长度为 1」，而是「长度 ≤ 1」。写成 if (l >= r) 最稳妥，对应左闭右开区间；若用左闭右闭（[l, r]），出口就得是 if (l >= r) 或 if (l == r)，但后者会漏掉空区间，引发未定义行为。
使用场景：当数组为空（size() == 0）或单元素时，必须立刻返回，否则递归栈溢出或访问 arr[l] 崩溃。
立即学习“C++免费学习笔记（深入）”；
- 推荐统一用左闭右开：调用入口是
merge_sort(arr, 0, arr.size()) -
mid = l + (r - l) / 2，不用(l + r) / 2——防整数溢出（尤其size_t大数组） - 递归调用写成
merge_sort(arr, l, mid)和merge_sort(arr, mid, r)，严格对齐区间语义
原地归并能做到真 O(1) 额外空间吗
不能。教科书说「归并排序空间复杂度 O(n)」是对的——哪怕你试图复用原数组做中转，合并过程仍需一块大小为 r - l 的临时缓冲区。所谓“原地归并”算法（如 Block Sort）存在，但实现复杂、常数极大，C++ 标准库没提供，也不适合教学或一般工程场景。
性能影响：每层递归都分配 vector 或 new[] 临时内存，频繁堆分配会拖慢速度；更优做法是在顶层预分配一个和原数组等长的 temp，所有合并共用它。
- 不要在每次
merge里vector<int> temp(r - l)</int>——分配开销压倒算法本身 - 把
temp作为参数传入递归函数，或封装进类成员，避免重复构造/析构 - 若确定只排序
vector，直接用vector成员变量缓存，比裸指针 +new更安全
STL 的 stable_sort 就是归并排序吗
不完全是。libstdc++（GCC）和 libc++（Clang）的 std::stable_sort 在多数情况下用混合策略：小数组（通常 ≤ 64 元素）走插入排序，大数组用归并，但底层可能引入优化如“底向上归并”或“内省式切换”。它稳定、高效，但不保证一定是传统递归归并。
兼容性影响：如果你依赖归并的「最坏 O(n log n)」或特定分段行为（比如调试分治过程），别直接用 stable_sort 替代手写；但若只要稳定排序结果，它比手写更可靠、更适应各种数据分布。
- 调用
std::stable_sort(v.begin(), v.end())即可，无需自己实现 - 它支持自定义比较器，和
sort用法完全一致 - 注意：它不保证是归并——某些旧版 MSVC 实现曾用平衡二叉树模拟稳定排序，虽已淘汰，但说明标准只要求接口行为，不约束算法
真正难的不是写对 merge，而是想清楚每次合并时「哪段数据还没读」「哪段已经写死」「临时空间从哪来又还给谁」——这几个状态一旦错位，bug 就藏得深，还随数据规模变化而时隐时现。
