inplace_merge：不靠额外空间，把两段有序序列“缝”成一段

上周帮同事调一个性能瓶颈，发现他用 vector 存了两段已排序的数据，想合并后去重。他先 insert 第二段、再 sort 全局——10 万条数据，耗时 80ms。我顺手改成 inplace_merge，时间压到 3ms，内存零新增。他盯着结果愣了三秒：“这函数……居然真能原地合？”

是的，std::inplace_merge 是 C++ 标准库里少有的、真正意义上“原地”完成归并操作的算法。它不申请新容器，不拷贝整段数据，只靠交换和移动，在 O(n) 额外空间（注意：不是 O(1)！但远小于 n）下完成合并。可偏偏很多人只在面试题里见过它，写业务代码时却绕着走——要么怕它难懂，要么误以为它只是 sort 的平替。

我们来把它“拆开看”。

inplace_merge 的签名很干净：

template<class BidirIt>
void inplace_merge(BidirIt first, BidirIt middle, BidirIt last);

template<class BidirIt, class Compare>
void inplace_merge(BidirIt first, BidirIt middle, BidirIt last, Compare comp);

关键不在参数，而在语义：[first, middle) 和 [middle, last) 必须各自有序，函数会把它们合并成一个整体有序的 [first, last)，且所有元素仍在原位置上。

这里有个极易被忽略的前提：它不要求整个区间初始有序，只要求以 middle 为界的两段分别有序。比如 vector<int>{1,3,5,2,4,6}，middle 指向第 3 个元素（即 5 后面），那么前段 {1,3,5}、后段 {2,4,6} 都有序，inplace_merge 就能直接工作——它处理的是“天然分段有序”的场景，不是通用排序器。

实际中这类场景不少：

• 日志按小时切片写入，每片内按时间戳排好，需要按天合并展示；
• 多线程分别对子数组排序后，主控线程需合并结果；
• 增量数据插入有序容器末尾，再触发一次局部归并。

它内部怎么做的？标准没规定具体实现，但主流 libstdc++ 和 libc++ 都采用一种叫 “缓冲区归并”（buffered merge） 的策略：
优先尝试用小块临时空间（比如栈上分配 1KB 缓冲区）加速；若不够，则退化为“旋转+归并”——把较小那段挪到前面当临时区，再逐个归并回填。整个过程只做元素移动（move）或交换（swap），不构造新对象。

这意味着什么？
✅ 对 std::string、std::vector 等含资源的对象，move 成本远低于 copy；
✅ 若你的类型禁用了移动（如 std::array<std::mutex, 10>），它仍能靠 swap 完成，只是稍慢；
❌ 但它不能替代 std::merge——后者输出到新容器，适合需要保留原数据的场景；也不能替代 std::sort——它不解决无序输入。

一个真实踩坑点：有人传入 middle == first 或 middle == last。这时逻辑上是一段空区间，inplace_merge 会直接返回，没问题。但若 middle 指向非法位置（比如越界），行为未定义——它不做边界检查，像所有 STL 算法一样，信任你传入合法迭代器。

再看一个实用技巧：如何合并多个有序段？
比如有 4 段：[a,b), [b,c), [c,d), [d,e)。别傻傻调四次 inplace_merge。正确姿势是分治：

inplace_merge(a, b, c); // 合并前两段 → [a,c)
inplace_merge(a, c, d); // 合并前三段 → [a,d)
inplace_merge(a, d, e); // 合并全部 → [a,e)

时间复杂度仍是 O(n)，但常数更优，且避免中间状态碎片化。

最后说说性能直觉：

• 当两段长度悬殊（比如 1000 vs 10），inplace_merge 会自动优化——短段作为“驱动段”，减少移动次数；
• 若你提前知道某段极小（< 16 个元素），手动用插入排序预处理，有时比依赖 inplace_merge 内部判断更快；
• 在 std::deque 上用它？可以，但性能未必好——双向链表的随机访问代价高，此时 std::merge + assign 反而更稳。

回到开头那个例子：为什么从 80ms 到 3ms？因为 sort 是 O(n log n)，而 inplace_merge 是 O(n)，且缓存友好——它顺序扫描、局部移动，CPU 预取效率高；而 sort 的跳跃访问让 L1 缓存频繁失效。

所以，下次看到“两段有序，要合成一段”，别条件反射去 insert + sort。停下来，确认下迭代器范围，敲一行 inplace_merge。它不炫技，不造概念，就安安静静把你省下的内存和毫秒，还给用户滑动列表时那一点不易察觉的顺滑。