< cpp‎ | algorithm‎ | ranges
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy, ranges::sort, ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
Search operations
(C++11)                (C++11)(C++11)

Modifying sequence operations
Copy operations
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17)(C++11)
Sampling operations

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Lexicographical comparison operations
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Constrained algorithms
All names in this menu belong to namespace std::ranges
Non-modifying sequence operations
Modifying sequence operations
Partitioning operations
Sorting operations
Binary search operations (on sorted ranges)
Set operations (on sorted ranges)
Heap operations
Minimum/maximum operations
Permutation operations
Fold operations
Numeric operations
Operations on uninitialized storage
Return types
Defined in header <algorithm>
Call signature
template< std::bidirectional_iterator I, std::sentinel_for<I> S,

          class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
    I inplace_merge( I first, I middle, S last,

                     Comp comp = {}, Proj proj = {} );
(1) (since C++20)
(constexpr since C++26)
template< ranges::bidirectional_range R, class Comp = ranges::less,

          class Proj = std::identity >
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    inplace_merge( R&& r, ranges::iterator_t<R> middle,

                   Comp comp = {}, Proj proj = {} );
(2) (since C++20)
(constexpr since C++26)

Merges two consecutive sorted ranges [firstmiddle) and [middlelast) into one sorted range [firstlast).

A sequence is said to be sorted with respect to the comparator comp and projection proj if for any iterator it pointing to the sequence and any non-negative integer n such that it + n is a valid iterator pointing to an element of the sequence, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it))) evaluates to false.

This merge function is stable, which means that for equivalent elements in the original two ranges, the elements from the first range (preserving their original order) precede the elements from the second range (preserving their original order).

1) Elements are compared using the given binary comparison function comp and projection object proj, and the ranges must be sorted with respect to the same.
2) Same as (1), but uses r as the range, as if using ranges::begin(r) as first, and ranges::end(r) as last.

The function-like entities described on this page are niebloids, that is:

In practice, they may be implemented as function objects, or with special compiler extensions.


[edit] Parameters

first - the beginning of the first sorted range
middle - the end of the first range and the beginning of the second range
last - the end of the second sorted range
r - the range of elements to merge inplace
comp - comparison to apply to the projected elements
proj - projection to apply to the elements in the range

[edit] Return value

An iterator equal to last.

[edit] Complexity

Exactly N − 1 comparisons, if additional memory buffer is available, where N = ranges::distance(first, last). Otherwise, 𝓞(N•log(N)) comparisons. Additionally, twice as many projections as comparisons in both cases.

[edit] Notes

This function attempts to allocate a temporary buffer. If the allocation fails, the less efficient algorithm is chosen.

Feature-test macro Value Std Feature
__cpp_lib_constexpr_algorithms 202306L constexpr stable sorting

[edit] Possible implementation

This implementation only shows the slower algorithm used when no additional memory is available. See also the implementation in MSVC STL and libstdc++.

struct inplace_merge_fn
    template<std::bidirectional_iterator I, std::sentinel_for<I> S,
             class Comp = ranges::less, class Proj = std::identity>
    requires std::sortable<I, Comp, Proj>
    constexpr I operator()(I first, I middle, S last, Comp comp = {}, Proj proj = {}) const
        I last_it = ranges::next(middle, last);
        inplace_merge_slow(first, middle, last_it,
                           ranges::distance(first, middle),
                           ranges::distance(middle, last_it),
                           std::ref(comp), std::ref(proj));
        return last_it;
    template<ranges::bidirectional_range R, class Comp = ranges::less,
             class Proj = std::identity>
    requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
    constexpr ranges::borrowed_iterator_t<R>
        operator()(R&& r, ranges::iterator_t<R> middle,
                   Comp comp = {}, Proj proj = {}) const
        return (*this)(ranges::begin(r), std::move(middle), ranges::end(r),
                       std::move(comp), std::move(proj));
    template<class I, class Comp, class Proj>
    static constexpr void inplace_merge_slow(I first, I middle, I last, 
                                             std::iter_difference_t<I> n1,
                                             std::iter_difference_t<I> n2,
                                             Comp comp, Proj proj)
        if (n1 == 0 || n2 == 0)
        if (n1 + n2 == 2 && comp(proj(*middle), proj(*first)))
            ranges::iter_swap(first, middle);
        I cut1 = first, cut2 = middle;
        std::iter_difference_t<I> d1{}, d2{};
        if (n1 > n2)
            d1 = n1 / 2;
            ranges::advance(cut1, d1);
            cut2 = ranges::lower_bound(middle, last, *cut1,
                                       std::ref(comp), std::ref(proj));
            d2 = ranges::distance(middle, cut2);
            d2 = n2 / 2;
            ranges::advance(cut2, d2);
            cut1 = ranges::upper_bound(first, middle, *cut2,
                                       std::ref(comp), std::ref(proj));
            d1 = ranges::distance(first, cut1);
        I new_middle = ranges::rotate(cut1, middle, cut2);
        inplace_merge_slow(first, cut1, new_middle, d1, d2,
                           std::ref(comp), std::ref(proj));
        inplace_merge_slow(new_middle, cut2, last, n1 - d1, n2 - d2,
                           std::ref(comp), std::ref(proj));
inline constexpr inplace_merge_fn inplace_merge {};

[edit] Example

#include <algorithm>
#include <complex>
#include <functional>
#include <iostream>
#include <iterator>
#include <vector>
void print(auto const& v, auto const& rem, int middle = -1)
    for (int i{}; auto n : v)
        std::cout << (i++ == middle ? "│ " : "") << n << ' ';
    std::cout << rem << '\n';
template<std::random_access_iterator I, std::sentinel_for<I> S>
requires std::sortable<I>
void merge_sort(I first, S last)
    if (last - first > 1)
        I middle{first + (last - first) / 2};
        merge_sort(first, middle);
        merge_sort(middle, last);
        std::ranges::inplace_merge(first, middle, last);
int main()
    // custom merge-sort demo
    std::vector v{8, 2, 0, 4, 9, 8, 1, 7, 3};
    print(v, ": before sort");
    merge_sort(v.begin(), v.end());
    print(v, ": after sort\n");
    // merging with comparison function object and projection
    using CI = std::complex<int>;
    std::vector<CI> r{{0,1}, {0,2}, {0,3}, {1,1}, {1,2}};
    const auto middle{std::ranges::next(r.begin(), 3)};
    auto comp{std::ranges::less{}};
    auto proj{[](CI z) { return z.imag(); }};
    print(r, ": before merge", middle - r.begin());
    std::ranges::inplace_merge(r, middle, comp, proj);
    print(r, ": after merge");


8 2 0 4 9 8 1 7 3 : before sort
0 1 2 3 4 7 8 8 9 : after sort
(0,1) (0,2) (0,3) │ (1,1) (1,2) : before merge
(0,1) (1,1) (0,2) (1,2) (0,3) : after merge

[edit] See also

merges two sorted ranges
computes the union of two sets
checks whether a range is sorted into ascending order
sorts a range into ascending order
merges two ordered ranges in-place
(function template) [edit]