在C++ STL中，merge和inplace_merge都用来处理已排序序列的合并操作，但二者在内存使用方式和调用形式上有明显差异。掌握它们的使用技巧，可以避免不必要的拷贝并提升程序性能。
merge算法基础用法
merge接受两个输入有序区间，将结果写入第三个区间。输入区间不会被改变，目标区间必须拥有足够空间。
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> a = {1, 3, 5};
std::vector<int> b = {2, 4, 6};
std::vector<int> out(a.size() + b.size());
// 将a和b合并到out中
std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin());
for (int v : out) {
std::cout << v << " ";
}
return 0;
}
使用自定义比较函数
当元素类型不支持默认小于比较，或需要降序合并时，可传入二元谓词。
#include <vector>
#include <algorithm>
bool cmp(int x, int y) {
return x > y; // 降序
}
void demo() {
std::vector<int> a = {5, 3, 1};
std::vector<int> b = {6, 4, 2};
std::vector<int> out(6);
std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin(), cmp);
}
inplace_merge原地合并技巧
inplace_merge用于同一个序列中两段相邻的有序子序列，将它们原地合并为一段完整有序序列，不需要额外输出空间。
#include <vector>
#include <algorithm>
#include <iostream>
int main() {
std::vector<int> v = {1, 3, 5, 2, 4, 6};
// 前半段[0,3)有序，后半段[3,6)有序
std::inplace_merge(v.begin(), v.begin() + 3, v.end());
for (int x : v) {
std::cout << x << " ";
}
return 0;
}
稳定性与复杂度
两个算法都是稳定排序相关操作，相等元素的相对顺序保持不变。merge时间复杂度为线性，inplace_merge最坏情况需要额外内存或更多移动。
| 算法 | 额外空间 | 典型用途 |
|---|---|---|
| merge | 需要输出区 | 归并两个独立有序集 |
| inplace_merge | 原地处理 | 同一序列分段排序后合并 |
常见错误与建议
- 忘记输入区间必须已排序，否则结果未定义。
- 使用merge时目标容器未预留空间，导致写入越界。
- inplace_merge的middle迭代器必须正确指向第二段起始。
在内存充足且来源独立的场景优先用merge；当需要在原数组完成归并排序的最后一步时，inplace_merge更合适。
实际编码中，建议先用空函数测试迭代器边界，再填入业务逻辑。
C++_STLmergeinplace_merge修改时间：2026-07-28 00:03:42