Namespaces
Variants

    std::inplace_merge

    来自 zh.cppreference.net
     
    C++
     
    算法库
    受约束算法和范围算法 (C++20)
    受约束算法，例如 ranges::copy、ranges::sort，...
    排序和相关操作
    划分操作
    (C++11)    
    (C++11)

    排序操作
    二分查找操作
    (在已划分的范围上)
    集合操作（在已排序范围上）
    合并操作（在已排序范围上）
    堆操作
    最小/最大操作
    (C++11)
    (C++17)
    字典序比较操作
    (C++20)
    排列操作


     
    定义于头文件 <algorithm> 
    template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );
    		(1) (自 C++26 起 constexpr) 
    template< class ExecutionPolicy, class BidirIt >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last );
    		(2) (C++17 起) 
    template< class BidirIt, class Compare >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last,
                    Compare comp );
    		(3) (自 C++26 起 constexpr) 
    template< class ExecutionPolicy, class BidirIt, class Compare >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last,
                    Compare comp );
    		(4) (C++17 起)

    合并两个连续的有序范围 [first, middle) 和 [middle, last) 到一个有序范围 [first, last)。

    1) 如果 [first, middle) 或 [middle, last) 没有根据 排序（按 operator<(C++20 前)std::less{}(C++20 起)），则行为未定义。
    3) 如果 [first, middle) 或 [middle, last) 没有根据 comp 排序，则行为未定义。
    2,4) 与 (1,3) 相同，但按 policy 执行。
    这些重载仅当满足以下表达式的值为 true 时才会参与重载决议：

    std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>

    		(C++20 前)

    std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>

    		(C++20 起)

    此合并函数是稳定的，意味着对于两个原始范围中相等的元素，第一个范围中的元素（保持其原始顺序）排在第二个范围中的元素（保持其原始顺序）之前。

    如果满足以下任何条件，则行为未定义：

    (C++11 前)
    (C++11 起)

    参数

    first - 第一个有序范围的起始
    middle - 第一个有序范围的结束和第二个有序范围的起始
    last - 第二个有序范围的结束
    policy - 要使用的 执行策略
    comp - 比较函数对象（即满足 Compare 要求的对象），当第一个参数 true 于第二个参数时（即顺序 在前 时）返回 true。

    比较函数的签名应等价于以下形式：

    bool cmp(const Type1& a, const Type2& b);

    虽然签名不必包含 const&，但函数不能修改传递给它的对象，并且必须能够接受类型（可能为 const）Type1 和 Type2 的所有值，无论 值类别如何（因此不允许使用 Type1&，也不允许使用 Type1，除非 Type1移动等价于复制(C++11 起)）。
    类型 Type1 和 Type2 必须使得类型 BidirIt 的对象可以解引用并隐式转换为这两种类型。 ​

    类型要求
    -
    BidirIt 必须满足 LegacyBidirectionalIterator 的要求。
    -
    Compare 必须满足 Compare 的要求。

    复杂度

    给定 N 为 std::distance(first, last)：

    1) 如果有足够额外内存可用，则正好进行 N-1 次比较（使用 operator<(C++20 前)std::less{}(C++20 起)）；否则进行 O(N⋅log(N)) 次比较。
    2) O(N⋅log(N)) 次比较（使用 operator<(C++20 前)std::less{}(C++20 起)）。
    3) 如果有足够额外内存可用，则正好调用 N-1 次比较函数 comp；否则调用 O(N⋅log(N)) 次。
    4) O(N⋅log(N)) 次调用比较函数 comp。

    异常

    带有模板参数名为 ExecutionPolicy 的重载按如下方式报告错误：

    • 如果作为算法一部分调用的函数抛出异常，且 ExecutionPolicy 是 标准策略之一，则调用 std::terminate。对于任何其他 ExecutionPolicy，行为由实现定义。
    • 如果算法无法分配内存，则抛出 std::bad_alloc。

    可能的实现

    参见 libstdc++ 和 libc++ 中的实现。

    注解

    此函数尝试分配一个临时缓冲区。如果分配失败，则选用效率较低的算法。

    功能特性测试宏 值 标准 功能特性
    __cpp_lib_constexpr_algorithms 202306L (C++26) constexpr 原地合并 (1)、(3)

    示例

    以下代码是归并排序的一种实现。

    运行此代码
    #include <algorithm>
#include <iostream>
#include <vector>

template<class Iter>
void merge_sort(Iter first, Iter last)
{
    if (last - first > 1)
    {
        Iter middle = first + (last - first) / 2;
        merge_sort(first, middle);
        merge_sort(middle, last);
        std::inplace_merge(first, middle, last);
    }
}

int main()
{
    std::vector<int> v{8, 2, -2, 0, 11, 11, 1, 7, 3};
    merge_sort(v.begin(), v.end());
    for (const auto& n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}

    输出： 

    -2 0 1 2 3 7 8 11 11

    参阅

    		 合并两个有序范围
    (函数模板 & 算法函数对象)
    (C++20)
    		对元素范围进行排序
    (函数模板 & 算法函数对象)
    (C++20)
    		对元素范围进行排序，同时保持相等元素之间的相对顺序
    (函数模板 & 算法函数对象)
    (C++20)
    (C++20)
    		 原地合并两个有序范围
    (算法函数对象)