C++合并两个已排序vector 求优于拼接后排序的实现方法

现有方案的缺陷 #

当前实现存在两处问题：

• 第二处遍历循环的终止条件写为i < v1.size()，实际目的是遍历v2的所有元素，一旦v2长度小于v1，会直接越界访问无效内存，触发未定义行为
• 拼接完成后再整体调用sort的时间复杂度为O((n+m)log(n+m))，没有利用“两个输入本身已经有序”的前置条件，整体效率偏低

优化实现 #

利用两个输入本身的有序特性，可以将合并的时间复杂度降到O(n+m)，远优于整体排序的方案，可选择的实现方式有两种：

直接使用STL内置的std::merge算法 #

这是STL为有序区间合并提供的标准接口，边界处理可靠，不需要手动维护指针逻辑：

#include <vector>
#include <algorithm>
#include <iterator>

std::vector<int> v1 = {1, 3};
std::vector<int> v2 = {2};
std::vector<int> v3;
// 提前预留总容量，避免vector扩容时的反复内存拷贝
v3.reserve(v1.size() + v2.size());
// 按升序合并两个有序区间，输出到v3
std::merge(
    v1.cbegin(), v1.cend(),
    v2.cbegin(), v2.cend(),
    std::back_inserter(v3)
);

注意：调用std::merge前需要保证两个输入区间的排序规则和输出要求一致（默认升序），完全匹配当前的使用场景。

手动实现双指针合并 #

如果需要自定义合并规则，可以自行实现双指针逻辑，核心思路和std::merge的底层实现一致：

• 初始化两个指针分别指向两个vector的起始位置
• 每次比较两个指针指向的元素，将更小的元素追加到结果vector，同时将对应指针后移
• 当其中一个指针走到末尾时，直接把另一个vector的剩余元素全部追加到结果（剩余元素本身已经有序，不需要再做比较）
  示例代码：

std::vector<int> v3;
v3.reserve(v1.size() + v2.size());
size_t idx1 = 0, idx2 = 0;
// 两个指针都未到末尾时，逐次比较取较小值
while (idx1 < v1.size() && idx2 < v2.size()) {
    if (v1[idx1] <= v2[idx2]) {
        v3.push_back(v1[idx1++]);
    } else {
        v3.push_back(v2[idx2++]);
    }
}
// 追加v1的剩余元素
while (idx1 < v1.size()) {
    v3.push_back(v1[idx1++]);
}
// 追加v2的剩余元素
while (idx2 < v2.size()) {
    v3.push_back(v2[idx2++]);
}

内容的提问来源于stack exchange，提问作者Ranjeet Hinge