Skip to content
Tutorials Center
My learning

Topics

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.

C++
std::vector<int> out(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin());

Try it

C++ Merging two sorted vectors

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.

C++ inplace_merge and a merge sort

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

C++
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: merge does at most N1 + N2 - 1 comparisons. inplace_merge is 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 use std::back_inserter. Calling merge with out.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; merge keeps every element, duplicates included.
  • std::list has a member merge that splices nodes without copying elements and empties the other list.
  • Ranges: std::ranges::merge and inplace_merge (C++20) take ranges plus projections.