std::inplace_merge 是什么，它合并的是哪两段？
std::inplace_merge 不是把两个独立容器合并，而是把**同一个容器中相邻的两段已排序子序列**合并成一段有序序列。关键在于“同一容器”和“相邻”——它操作的是一个 RandomAccessIterator 范围，且要求：[first, middle) 和 [middle, last) 都各自升序（默认）或按给定比较器有序。
常见误用是试图用它合并 vector 和 vector，这不行；它不接受两个分离容器，也不重分配内存。
基本调用方式与参数含义
最常用重载形式：
std::inplace_merge(first, middle, last);
其中：
立即学习“C++免费学习笔记（深入）”；
-
first指向整个待合并区间的开头 -
middle指向第一段有序区间的末尾后一位置（即第二段起点） -
last指向整个区间的末尾后一位置
例如：vector = {1,3,5,2,4,6}，前 3 个和后 3 个各自有序，则应传入 v.begin(), v.begin()+3, v.end()。
支持自定义比较器的版本：
std::inplace_merge(first, middle, last, comp);
comp(a, b) 应返回 true 当 a 应排在 b 前面（即升序逻辑）。若原两段是降序，comp 必须一致，否则行为未定义。
为什么有时性能差？临时缓冲区的影响
std::inplace_merge 名义上“原地”，但标准不禁止它使用额外空间。实际实现（如 libstdc++、libc++）通常会尝试分配一块临时缓冲区来加速——如果分配失败或太小，会回落到 O(n log n) 的分治合并（类似归并排序的合并步骤但带旋转）；若有足够缓冲区，则做到 O(n) 时间 + O(min(m,n)) 额外空间（m、n 是两段长度）。
这意味着：
- 对小数据（比如几十个元素），开销可能比手写循环还高
- 在内存受限环境（如嵌入式），需注意其可能抛
std::bad_alloc - 没有“强制纯原地（零额外内存）”模式；若真需要，得自己实现旋转+归并的算法
常见错误和调试线索
运行时没报错但结果乱序？大概率是输入前提不满足。典型问题：
- 两段不相邻：比如中间插了未排序元素 → 合并范围错，结果不可预测
- 某一段本身无序：比如
{1,5,3}声称是有序段 → 行为未定义 - 迭代器失效：在
vector上调用期间有push_back或resize→ 迭代器悬空，UB - 传错
middle：比如本该是v.begin()+4却写了v.begin()+5→ 一段变长、一段变短，破坏前提
调试建议：合并前用 std::is_sorted 分别检查两段：
assert(std::is_sorted(first, middle));
assert(std::is_sorted(middle, last));
不是生产环境常规做法，但定位问题极快。
真正要注意的是：它不校验前提，也不告诉你哪错了。只要两段不满足有序+相邻，结果就只是“未定义”，而不是抛异常或断言失败。
