Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::inplace_merge: stable merge of adjacent runs

std::inplace_merge stably merges two consecutive, already sorted subranges into the same range.

Version: C++23

Syntax

template<class BidirectionalIt>
void std::inplace_merge(BidirectionalIt first, BidirectionalIt middle, BidirectionalIt last);

template<class BidirectionalIt, class Compare>
void std::inplace_merge(BidirectionalIt first, BidirectionalIt middle, BidirectionalIt last, Compare comp);

std::inplace_merge(first,middle,last) merges [first,middle) and [middle,last) using std::less; another overload accepts comp. Both subranges must be valid and separately sorted under the same ordering. The result occupies [first,last) and is stable: equivalent elements from the first run remain before equivalent ones from the second.

The example has runs 1,4,7 and 2,3,8; after merging it prints 1 2 3 4 7 8. middle marks the input boundary, not a position preserved in the result.

Violating the sorted precondition is undefined behavior. The algorithm requires bidirectional iterators and movable, swappable values. Without a policy and with enough auxiliary memory it performs exactly N−1 comparisons; buffer unavailability falls back to the no-buffer algorithm with up to O(N log N) comparisons, while other exceptions propagate. With a standard execution policy, an uncaught element-operation exception calls std::terminate, whereas unavailable temporary memory for parallel execution can throw std::bad_alloc.

Examples

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{1, 4, 7, 2, 3, 8};
    std::inplace_merge(values.begin(), values.begin() + 3, values.end());
    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
}

Result

1 2 3 4 7 8 

std::inplace_merge → 1 2 3 4 7 8

Sources