Daily bit(e) of C++ | std::inplace_merge

Daily bit(e) of C++ ♻️29, The in-place merge algorithm: std::inplace_merge.

The std::inplace_merge algorithm merges two sorted subranges into one sorted range.

With this algorithm, we can quickly build a merge-sort implementation (as the in-place merge is the core of this sort).

The merge is stable (maintains the order of equal elements), making the sort implementation stable as well.

The algorithm has both a parallel C++17 and range C++20 version.

#include <concepts>
#include <ranges>
#include <algorithm>

void merge_sort(std::ranges::random_access_range auto& rng) {
    if (rng.size() <= 1) return;

    // divide the range into two parts
    auto mid = rng.begin() + rng.size()/2;
    auto left = std::ranges::subrange(rng.begin(), mid);
    auto right = std::ranges::subrange(mid, rng.end());

    // recursive sort left and right
    merge_sort(left);
    merge_sort(right);
    // in-place merge left and right
    std::ranges::inplace_merge(rng, mid);
}

Open the example in Compiler Explorer.