算法库：归并函数

函数	用途	输入要求	输出位置	稳定性	时间复杂度
std::merge	归并两个独立的有序序列	输入范围、输出迭代器	新容器（输出）	稳定	O(n) 比较
std::inplace_merge	归并同一序列内的两个相邻有序段	同一序列的两个相邻子范围	输入序列原地	稳定	O(n) 或 O(n log n)
std::stable_sort	稳定排序整个序列	需要排序的整个范围	输入序列原地	稳定	平均 O(n log n)

---

🔹 std::merge：合并两个独立的有序序列

该算法将两个已排序的范围归并，结果存放到一个新位置，所以需要预先为目标容器分配足够的内存。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v1 = {1, 3, 5};
    std::vector<int> v2 = {2, 4, 6};
    std::vector<int> merged(v1.size() + v2.size()); // 分配足够空间

    // 归并两个有序 vector
    std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), merged.begin());

    // 输出：1 2 3 4 5 6
    for (int i : merged) std::cout << i << " ";
    return 0;
}

• 性能：它的比较次数至多为 len1 + len2 - 1次，比 inplace_merge 更快，是合并两个独立有序数组的首选方法。

🔹 std::inplace_merge：原地归并同一序列的相邻两段

它原地（即在原内存空间）归并同一容器中两个相邻且已排序的连续范围，避免额外的大内存开销。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 前一半 [1, 3, 5] 和后一半 [2, 4, 6] 各自有序，但整体无序
    std::vector<int> v = {1, 3, 5, 2, 4, 6};
    auto middle = v.begin() + 3; // 指向 2

    // 原地归并
    std::inplace_merge(v.begin(), middle, v.end());

    // 输出：1 2 3 4 5 6
    for (int i : v) std::cout << i << " ";
    return 0;
}

• 性能：如果分配足够内存，归并比较次数精确为 N-1（N为总元素数）；否则最坏为 O(N log N)。它最适合在同一容器中对数据分段操作后，再整体合并。

🔹 std::stable_sort：稳定的归并排序

该函数是 C++ 提供的稳定排序。它以归并排序为底层算法，保持相等元素的相对顺序，且最坏情况下时间复杂度始终保持在 O(N log N)。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {5, 2, 8, 2, 1};

    // 稳定排序整个容器
    std::stable_sort(v.begin(), v.end());

    // 输出：1 2 2 5 8
    for (int i : v) std::cout << i << " ";
    return 0;
}

• 关键对比：它与 std::sort 的主要区别在于稳定性（sort 不保证稳定）和内存开销（sort 空间为 O(log N)，stable_sort 为 O(N)）。

---

💎 总结：使用场景速查

场景	推荐函数
归并两个完全独立的已排序数组	std::merge
在同一容器中，对两个相邻的有序段进行整体排序	std::inplace_merge
需要对整个序列进行稳定排序（如结构体按年龄排序后，同年龄的人保持原顺序）	std::stable_sort
合并多个已排序序列（多路归并）	std::priority_queue
需要将归并结果输出到流或其他迭代器	std::merge
不关心排序稳定性，只追求极致速度	std::sort