<p>std::inplace_merge 需左段[left, mid)、右段[mid, right)，目标区间有效且支持随机访问；手写 merge 时临时数组大小为 right - left，终止条件用 left >= right 更安全；原地归并实际多用 O(n) 辅助空间。</p>
merge 函数怎么配对 sort 使用才不崩
标准库 std::inplace_merge 或手写 merge 时，最常崩在区间边界错位：左段右开、右段右开、合并目标空间没预留——三者只要一个对不上，std::copy 或循环就踩内存。
- 左子数组范围必须是
[left, mid)（不是[left, mid]），右子数组是[mid, right) - 如果用
std::inplace_merge，确保容器支持随机访问且迭代器有效，vector安全，list得用它自己的merge成员函数 - 手写
merge时，临时数组大小必须是right - left，别用mid - left + right - mid算——看着一样，但整型溢出或负偏移时会静默错
递归终止条件写成 left >= right 还是 left == right
写成 left >= right 更稳。归并排序分治的最小单位是长度为 1 的段，对应区间 [i, i+1)，此时 left == i，right == i+1，left 成立；一旦 <code>left == right，区间为空，直接返回。
- 若误写为
left == right，当输入空容器（begin == end）时，left == right成立，看似能过，但后续mid = left + (right - left) / 2在空区间下算出的mid仍合法，可能触发无意义递归或越界访问 -
left >= right能同时拦截空区间和错序区间（比如调用时传了反向迭代器） - 别信“长度为 0 或 1 都不用排”——归并里“不用排”只对应空区间，单元素区间必须参与 merge 步骤，否则合并逻辑断链
为什么原地归并（in-place merge）实际很少用
因为真·原地（O(1) 额外空间）归并存在，但常数极大，且标准库实现（如 std::inplace_merge）内部大概率用了 O(n) 辅助空间——它只是“对用户接口表现为原地”，底层仍分配临时缓冲区。
- 纯 O(1) 原地归并算法（如 Katajainen 等人提出的）需要大量旋转、翻转操作，比较次数远超经典归并，实测在 n > 1e4 时就比带辅助数组的慢 3 倍以上
-
std::inplace_merge在小数据量（right - left ）时会切到 insertion sort，这不是优化，是规避原地合并的高成本 - 真正要省空间，不如直接用
std::stable_sort——它在 libstdc++ 和 libc++ 中对随机访问迭代器默认就是归并变种，且自动管理临时内存
稳定性的关键不在 merge，而在拆分方式
归并排序天然稳定，但前提是 merge 过程中，当 left_arr[i] == right_arr[j] 时，必须优先取左段元素。这点容易被忽略，尤其手写时有人写成 或漏判相等情况。
立即学习“C++免费学习笔记（深入）”；
- 错误写法：
if (left_val —— 看似包含相等，但若 left_val 实际来自右段上一轮残留，逻辑已乱 - 正确守则：仅用
判断，相等一律取左段；或显式写 <code>if (left_val ，else 分支无条件取左 - 稳定性跟递归拆分无关（
mid取左中位还是右中位不影响），只取决于 merge 中相等元素的相对顺序是否保持
实际写的时候，最麻烦的不是递归结构，是 merge 循环里三个指针（左、右、目标）的步进时机和终止条件——多一行 ++ 或少一行 ++，就可能漏掉最后一个元素，或者写越界。
