std::merge用于合并两个独立有序区间到新容器，需额外空间且输出区域须足够大；std::inplace_merge则原地合并单个容器中两段相邻有序子区间，要求随机访问且不重叠。
std::merge 是非原地合并，需要额外空间
它把两个已排序的区间合并成一个新序列，结果写入第三个容器或内存区域。最常见用法是合并两个 std::vector 到第三个 std::vector 中。
容易踩的坑：
-
std::merge不修改输入区间，但要求输出迭代器指向的空间足够大（至少std::distance(first1, last1) + std::distance(first2, last2)） - 如果输出目标和某个输入区间重叠（比如把结果写回其中一个输入容器），行为未定义
- 必须确保两个输入区间各自有序，否则结果不可预测
示例：
std::vectora = {1, 3, 5}; std::vector b = {2, 4, 6}; std::vector out(6); std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin()); // out == {1,2,3,4,5,6}
std::inplace_merge 是原地合并，但要求输入连续且可随机访问
它把一个容器中**两段相邻的有序子区间**合并成一段有序区间，不分配新内存，但内部可能做元素移动或旋转操作。
立即学习“C++免费学习笔记（深入）”；
关键限制：
- 输入必须是单个连续容器（如
std::vector、std::deque），不能是两个分离容器 - 要指定一个分割点（middle 迭代器），使得
[first, middle)和[middle, last)各自有序 - 时间复杂度平均 O(n)，但最坏可能达 O(n log n)；空间复杂度 O(log n)（递归栈或缓冲区）
示例：
std::vectorv = {1, 3, 5, 2, 4, 6}; // 前3个有序，后3个有序 auto mid = v.begin() + 3; std::inplace_merge(v.begin(), mid, v.end()); // v == {1,2,3,4,5,6}
归并排序实现中该选哪个？
标准库没提供直接的归并排序函数，但你可以用这两个函数组合实现。实际选择取决于数据结构和内存约束：
- 若你手写分治式归并排序（如对
std::vector排序），通常用std::inplace_merge来合并左右子段——前提是它们在内存中相邻且已排好序 - 若你在处理两个独立的已排序序列（比如日志文件按时间合并），
std::merge更自然，也更安全 -
std::inplace_merge对std::list有特化版本（O(n) 时间、O(1) 额外空间），此时它比std::merge更省空间，但注意std::list::merge()成员函数才是为链表设计的首选
常见错误：误用 inplace_merge 导致未定义行为
最典型的错误是传入非相邻或非有序的区间，或者在不支持随机访问的容器（如 std::forward_list）上调用它。
例如：
- 对
std::forward_list调用std::inplace_merge—— 编译失败（无匹配重载） - 把
v.begin()+1当作 middle，但[v.begin(), v.begin()+1)或[v.begin()+1, v.end())实际并不有序 —— 结果混乱，无报错提示 - 用
std::inplace_merge处理两个std::array拼接后的视图（非真正连续内存）—— 行为未定义
调试时建议先用 std::is_sorted 检查左右两段是否真有序，再调用 std::inplace_merge。
真正难的不是调用哪个函数，而是保证传给它们的区间满足前提条件：有序性、连续性、可访问性。这些约束不会在编译时报错，但会在运行时悄悄破坏数据。
