std::inplace_merge

template< class BidirIt >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last );

template< class ExecutionPolicy, class BidirIt >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last );

template< class BidirIt, class Compare >
void inplace_merge( BidirIt first, BidirIt middle, BidirIt last,
                    Compare comp );

template< class ExecutionPolicy, class BidirIt, class Compare >
void inplace_merge( ExecutionPolicy&& policy,
                    BidirIt first, BidirIt middle, BidirIt last,
                    Compare comp );

2つの連続したソート済み範囲 [first, middle) と [middle, last) を1つのソート済み範囲 [first, last) にマージします。

このマージ関数は安定です。つまり、元の2つの範囲内の等価な要素について、最初の範囲の要素（元の順序を保持）が2番目の範囲の要素（元の順序を保持）よりも前に配置されます。

次の条件のいずれかが満たされる場合、動作は未定義です：

• [first, middle) または [middle, last) は有効な範囲ではありません。

引数

計算量

N\(\scriptsize N\) を としたときstd::distance(first, last)：

例外

テンプレートパラメータ ExecutionPolicy を持つオーバーロードは次のようにエラーを報告します：

• アルゴリズムの一部として呼び出された関数が例外をスローし、ExecutionPolicy が標準ポリシーの1つである場合、std::terminate が呼び出されます。他の ExecutionPolicy については、動作は処理系定義です。
• アルゴリズムがメモリの確保に失敗した場合、std::bad_alloc がスローされます。

実装例

実装は libstdc++ および libc++ を参照してください。

注記

この関数は一時バッファの確保を試みます。確保に失敗した場合、効率の低いアルゴリズムが選択されます。

例

#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

関連項目