C++ Reference ยท Algorithms
The std::merge and std::inplace_merge algorithms
Reference for C++ std::merge and std::inplace_merge: combine two sorted ranges into one sorted range, stability, complexity and the merge sort pattern.
std::merge combines two sorted input ranges into one sorted output range. It reads both inputs once, always taking the smaller front element, so the cost is linear in the total number of elements. The inputs are not modified, and the output must be a different range.
std::inplace_merge merges two consecutive sorted sub-ranges of the same container, [first, middle) and [middle, last), into one sorted range in place. It is the second half of a merge sort and the cheapest way to add a sorted block to an already sorted vector.
std::vector<int> out(a.size() + b.size()); std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin());
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.
Syntax
template<class InIt1, class InIt2, class OutIt> OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt out); template<class InIt1, class InIt2, class OutIt, class Compare> OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt out, Compare comp); template<class BidirIt> void inplace_merge(BidirIt first, BidirIt middle, BidirIt last); template<class BidirIt, class Compare> void inplace_merge(BidirIt first, BidirIt middle, BidirIt last, Compare comp);
| Name | Description |
|---|---|
first1, last1, first2, last2 |
The two sorted input ranges. |
out |
Output iterator. For merge it must have room for all elements (or be a back_inserter). |
first, middle, last |
[first, middle) and [middle, last) are both sorted. |
comp |
The ordering both inputs are sorted by (default <). |
Returns: merge returns the output iterator one past the last element written. inplace_merge returns nothing.
Errors / undefined behavior: the inputs must be sorted by comp; the output range of merge must not overlap either input. Writing past the end of the output container is undefined behavior.
Usage notes
- Stable: for equivalent elements, those from the first range come before those from the second. This is the guarantee that makes merge sort stable.
- Complexity:
mergedoes at most N1 + N2 - 1 comparisons.inplace_mergeis linear if it can allocate a buffer, and O(N log N) otherwise, so it may allocate memory. - Size the output first (
std::vector<int> out(n1 + n2)) or usestd::back_inserter. Callingmergewithout.begin()on an empty vector is a classic bug. - Different element types are fine as long as they are comparable and assignable to the output element type.
- Sorted set operations: if you want a union without duplicates, use
std::set_union;mergekeeps every element, duplicates included. std::listhas a membermergethat splices nodes without copying elements and empties the other list.- Ranges:
std::ranges::mergeandinplace_merge(C++20) take ranges plus projections.