std:: inplace_merge

Объединяет два последовательных отсортированных диапазона [ first , middle ) и [ middle , last ) в один отсортированный диапазон [ first , last ) .

Эта функция слияния является стабильной, что означает, что для эквивалентных элементов в исходных двух диапазонах элементы из первого диапазона (сохраняя свой исходный порядок) предшествуют элементам из второго диапазона (сохраняя свой исходный порядок).

Если выполняется любое из следующих условий, поведение не определено:

• [ 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

Смотрите также