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