std:: inplace_merge

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

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

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

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

パラメータ

計算量

与えられた \(\scriptsize N\) N を std:: distance ( first, last ) として：

例外

ExecutionPolicy という名前のテンプレートパラメータを持つオーバーロードは、 以下のようにエラーを報告します：

• アルゴリズムの一部として呼び出された関数の実行が例外をスローした場合、 ExecutionPolicy が 標準ポリシー のいずれかであるとき、 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

関連項目