Daily bit(e) C++. std::inplace_merge
Добавлено 16 апреля 2026 в 11:55
Daily bit(e) C++ 29. Алгоритм слияния на месте: std::inplace_merge.
Алгоритм std::inplace_merge объединяет два отсортированных поддиапазона в один отсортированный диапазон.
С помощью этого алгоритма мы можем быстро создать реализацию сортировки слиянием (поскольку слияние на месте является ядром этой сортировки).
Это слияние стабильно (сохраняет порядок равных элементов), что делает стабильной и реализацию сортировки.
У алгоритма есть как параллельная версия в C++17, так и версия для диапазонов в C++20.
#include <concepts>
#include <ranges>
#include <algorithm>
void merge_sort(std::ranges::random_access_range auto& rng) {
if (rng.size() <= 1) return;
// делим диапазон на две части
auto mid = rng.begin() + rng.size()/2;
auto left = std::ranges::subrange(rng.begin(), mid);
auto right = std::ranges::subrange(mid, rng.end());
// рекурсивно сортируем левую и правую части
merge_sort(left);
merge_sort(right);
// слияние на месте левой и правой частей
std::ranges::inplace_merge(rng, mid);
}