What is std::merge / std::inplace_merge in C++?

Merge two sorted ranges into a single sorted output range. Both std::merge and std::inplace_merge are stable and have been available since C++98.

Which C++ standard introduced std::merge / std::inplace_merge?

std::merge / std::inplace_merge was introduced in C++98.

What is the difficulty level of std::merge / std::inplace_merge?

std::merge / std::inplace_merge is considered Basic-level C++ material.

std::merge / std::inplace_merge

std::mergesince C++98

std::merge copies elements from two sorted input ranges into a single sorted output range, preserving the relative order of equivalent elements from each source — a stable operation.

Overview

The <algorithm> header provides two merge primitives that have been part of the standard since C++98:

std::merge — writes the merged result into a separate, non-overlapping output range.
std::inplace_merge — fuses two consecutive sorted sub-ranges within the same container in place, requiring bidirectional iterators.

Both algorithms are stable: when two elements compare equivalent, the element from the first range always precedes the element from the second in the output. This property is load-bearing in merge-sort implementations and in any context where a secondary ordering must survive the merge.

The default ordering uses operator<. A custom comparator overrides this, but both input ranges must be sorted with respect to the same comparator passed to the call.

C++17 added parallel execution-policy overloads for both algorithms. C++20 added std::ranges::merge and std::ranges::inplace_merge, which accept range objects and member projections directly.

Syntax

cpp

Godbolt

#include <algorithm>

// std::merge — separate output range (C++98)
template<class InputIt1, class InputIt2, class OutputIt>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first);

template<class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt merge(InputIt1 first1, InputIt1 last1,
               InputIt2 first2, InputIt2 last2,
               OutputIt d_first, Compare comp);

// Parallel overloads — ForwardIt replaces InputIt/OutputIt (C++17)
template<class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3>
ForwardIt3 merge(ExecutionPolicy&& policy,
                 ForwardIt1 first1, ForwardIt1 last1,
                 ForwardIt2 first2, ForwardIt2 last2,
                 ForwardIt3 d_first);

// std::inplace_merge — [first,middle) ∪ [middle,last) fused in place (C++98)
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);

// std::ranges::merge — range + projection interface (C++20)
namespace ranges {
    template<std::input_iterator I1, std::sentinel_for<I1> S1,
             std::input_iterator I2, std::sentinel_for<I2> S2,
             std::weakly_incrementable O,
             class Comp  = ranges::less,
             class Proj1 = std::identity,
             class Proj2 = std::identity>
    merge_result<I1, I2, O>
    merge(I1 first1, S1 last1, I2 first2, S2 last2, O result,
          Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});   // C++20

    // range-based overload also available                         // C++20
}

Return values:

std::merge — iterator to one past the last element written.
std::ranges::merge — in_in_out_result{in1, in2, out} with past-the-end iterators for both inputs and the output.
std::inplace_merge — void.

Examples

Merge into a pre-allocated buffer

cpp

Godbolt

#include <algorithm>
#include <vector>
#include <iterator>

int main() {
    std::vector<int> a{1, 3, 5, 7, 9};
    std::vector<int> b{2, 4, 6, 8, 10};

    std::vector<int> out;
    out.reserve(a.size() + b.size());  // avoids reallocation

    std::merge(a.begin(), a.end(),
               b.begin(), b.end(),
               std::back_inserter(out));
    // out == {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
}

Merging event streams by timestamp

A common real-world pattern: two independently sorted log streams arrive and must be combined in chronological order, with stream A taking precedence on ties.

cpp

Godbolt

#include <algorithm>
#include <vector>
#include <string>
#include <iterator>

struct Event {
    long long timestamp_us;
    std::string source;
    std::string payload;
};

std::vector<Event> merge_streams(std::vector<Event> a, std::vector<Event> b) {
    // precondition: both a and b are sorted by timestamp_us
    std::vector<Event> out;
    out.reserve(a.size() + b.size());

    std::merge(a.begin(), a.end(),
               b.begin(), b.end(),
               std::back_inserter(out),
               [](const Event& x, const Event& y) {
                   return x.timestamp_us < y.timestamp_us;
               });
    return out;
}

Stability guarantees that equal-timestamp events from a always precede those from b, preserving any source-priority semantics without extra work.

C++20 ranges::merge with member projections

Projections eliminate boilerplate comparators when the sort key is a data member.

cpp

Godbolt

#include <algorithm>
#include <vector>
#include <iterator>

struct Record {
    int   id;
    float score;
};

std::vector<Record> merge_records(std::vector<Record>& a,
                                   std::vector<Record>& b) {
    // both sorted ascending by id
    std::vector<Record> out;
    out.reserve(a.size() + b.size());

    std::ranges::merge(a, b,
                       std::back_inserter(out),
                       {},           // default comparator (ranges::less)
                       &Record::id,  // projection for first range   // C++20
                       &Record::id); // projection for second range  // C++20
    return out;
}

ranges::merge also returns in_in_out_result, making it composable with subsequent range operations without recomputing positions.

Bottom-up merge sort using std::inplace_merge

std::inplace_merge is the natural building block for a non-recursive, bottom-up merge sort. The two sub-ranges [first, middle) and [middle, last) must already be individually sorted:

cpp

Godbolt

#include <algorithm>
#include <vector>

void merge_sort(std::vector<int>& v) {
    const auto n = static_cast<std::ptrdiff_t>(v.size());
    for (std::ptrdiff_t width = 1; width < n; width *= 2) {
        for (std::ptrdiff_t lo = 0; lo < n; lo += 2 * width) {
            auto mid = std::min(lo + width, n);
            auto hi  = std::min(lo + 2 * width, n);
            std::inplace_merge(v.begin() + lo,
                               v.begin() + mid,
                               v.begin() + hi);
        }
    }
}

When the implementation can allocate a temporary buffer proportional to the range, the merge runs in O(n) time. It degrades to O(n log n) comparisons under memory pressure; the standard guarantees this as the worst-case bound.

Parallel merge (C++17)

cpp

Godbolt

#include <algorithm>
#include <execution>
#include <vector>

std::vector<int> parallel_merge(std::vector<int>& a, std::vector<int>& b) {
    std::vector<int> out(a.size() + b.size());

    std::merge(std::execution::par_unseq,  // C++17
               a.begin(), a.end(),
               b.begin(), b.end(),
               out.begin());
    return out;
}

par_unseq enables both multi-threading and SIMD vectorisation. Because std::merge writes each output element exactly once with no read-modify-write, it parallelises without contention. Output must be a pre-sized container; back_inserter is not valid with parallel policies.

Best Practices

Pre-sort or verify sorted order before merging. The precondition that both input ranges are sorted according to the same comparator is unchecked. Passing unsorted input yields undefined behavior with no diagnostic.

Reserve capacity before using back_inserter. Call out.reserve(a.size() + b.size()) before the merge. Without it each reallocation copies all previously merged elements, turning an O(n) copy into O(n log n) allocation work.

Use ranges::merge for new C++20 code. The in_in_out_result return type carries output position information without a separate std::distance call. Projections compose cleanly with struct members and lambdas.

Prefer the out-of-place form when performance matters. std::merge into a separate buffer avoids the O(n log n) fallback path that std::inplace_merge takes under allocation failure. Only use inplace_merge when a separate buffer is genuinely unavailable.

Match the comparator to the sort order. If the inputs were sorted with a descending comparator, the merge comparator must also be descending. A mismatch between sort order and merge comparator is a logic error the compiler cannot catch.

Common Pitfalls

Output range overlaps with input. std::merge requires the destination to be entirely disjoint from both input ranges. Aliasing produces undefined behavior. Use std::inplace_merge when merging within a single container.

Writing through a default-constructed iterator. std::merge(…, v.begin()) on an empty or undersized v is undefined. Either resize the destination to a.size() + b.size() before using v.begin(), or use std::back_inserter.

Confusing std::merge with std::set_union. std::merge copies all elements from both ranges, preserving duplicates. std::set_union copies each equivalent group at most max(count_in_a, count_in_b) times. If both inputs are sorted and deduplicated and the output must also be deduplicated, use set_union.

Assuming inplace_merge is always O(n). The O(n) path requires a temporary allocation proportional to the range size. On memory-constrained targets or when merging very large ranges, allocation failure triggers the O(n log n) fallback. Profile merge-heavy code on target hardware rather than assuming the fast path.

Passing parallel policy with back_inserter. Parallel algorithm overloads require forward iterators; back_insert_iterator is an output iterator only. Pre-size the output container and pass out.begin().

K-way Merge via priority_queue

Merging two sorted ranges is the degenerate case of a more general problem: merging k sorted ranges into one output. The standard library std::priority_queue (a max-heap by default) can be inverted into a min-heap by supplying std::greater as the comparator, giving O(n log k) total work for n elements across k ranges.

Each heap entry bundles the current element value together with the range index and the iterator pointing to the next element in that range. Whenever the minimum is popped, the iterator for the corresponding range is advanced and the next element (if any) is pushed back.

cpp

Godbolt

#include <algorithm>
#include <queue>
#include <vector>
#include <iterator>

// C++11
// Merges k sorted vectors into a single sorted output.
// Time: O(n log k) where n = total elements, k = number of ranges.
// Use case: merging sorted runs in an external sort pass.
std::vector<int> k_way_merge(const std::vector<std::vector<int>>& ranges) {
    using It = std::vector<int>::const_iterator;

    // Heap entry: (value, range_index, current_iterator)
    struct Entry {
        int value;
        std::size_t range_idx;
        It it;

        // min-heap: smallest value has highest priority
        bool operator>(const Entry& o) const { return value > o.value; }
    };

    std::priority_queue<Entry,
                        std::vector<Entry>,
                        std::greater<Entry>> heap;  // C++11

    // Seed the heap with the first element of each non-empty range.
    for (std::size_t i = 0; i < ranges.size(); ++i) {
        if (!ranges[i].empty())
            heap.push({ranges[i].front(), i, ranges[i].begin()});
    }

    std::vector<int> out;
    std::size_t total = 0;
    for (const auto& r : ranges) total += r.size();
    out.reserve(total);

    while (!heap.empty()) {
        auto [val, idx, it] = heap.top();  // C++17 structured binding
        heap.pop();
        out.push_back(val);

        // Advance and re-push if the range has more elements.
        ++it;
        if (it != ranges[idx].end())
            heap.push({*it, idx, it});
    }
    return out;
}

For two ranges this reduces to the familiar two-way merge, but the algorithm scales to hundreds of sorted files without modification. Each push/pop pair costs O(log k) comparisons, so the total complexity is O(n log k) regardless of how many ranges are present.

External Sort Pattern

When data exceeds available RAM, sorting must happen in two phases that both rely on merge as the core primitive. This is the strategy used by database systems, GNU sort, and distributed shuffle operations.

Phase 1 — create sorted runs. Read chunks of data small enough to fit in memory, sort each chunk, and write it to a temporary file. Each temporary file is one sorted run.

Phase 2 — k-way merge the runs. Open all run files simultaneously, use the k-way merge above to pull the global minimum repeatedly, and stream the result to the final output file. std::istream_iterator feeds std::merge directly from file streams without loading the full file into memory.

cpp

Godbolt

#include <algorithm>
#include <fstream>
#include <iterator>
#include <vector>
#include <string>
#include <filesystem>

// C++17
// Phase 1: sort a chunk of integers and write to a temp file.
// Returns the path of the file written.
std::string write_sorted_run(std::vector<int>& chunk, int run_id) {
    std::sort(chunk.begin(), chunk.end());  // C++98
    std::string path = "/tmp/run_" + std::to_string(run_id) + ".bin";
    std::ofstream out(path);
    for (int v : chunk) out << v << '\n';
    return path;
}

// Phase 2: merge exactly two sorted run files into one output file.
// For k > 2 files, apply the priority_queue approach from the section above.
void merge_two_run_files(const std::string& path_a,
                         const std::string& path_b,
                         const std::string& out_path) {
    std::ifstream fa(path_a), fb(path_b);
    std::ofstream fout(out_path);

    // istream_iterator provides single-pass input iteration over a file.  // C++98
    std::istream_iterator<int> ia(fa), ib(fb), end{};
    std::ostream_iterator<int> iout(fout, "\n");

    // std::merge reads lazily — only one element per range is in memory
    // at any time, making peak RAM proportional to k, not n.
    std::merge(ia, end, ib, end, iout);  // C++98
}

// Full external sort skeleton (two-run example).
void external_sort_example(const std::string& input_path,
                           const std::string& output_path) {
    constexpr std::size_t CHUNK = 1'000'000;  // fit in ~4 MB for int // C++14

    std::ifstream in(input_path);
    std::istream_iterator<int> src(in), eof{};

    std::vector<std::string> run_paths;
    int run_id = 0;

    // Phase 1
    while (src != eof) {
        std::vector<int> chunk;
        chunk.reserve(CHUNK);
        while (src != eof && chunk.size() < CHUNK)
            chunk.push_back(*src++);
        run_paths.push_back(write_sorted_run(chunk, run_id++));
    }

    // Phase 2 (simplified: assumes exactly 2 runs for illustration)
    if (run_paths.size() == 2) {
        merge_two_run_files(run_paths[0], run_paths[1], output_path);
    }
    // For run_paths.size() > 2, use the k_way_merge approach,
    // reading from istream_iterator<int> per file.

    for (const auto& p : run_paths)
        std::filesystem::remove(p);  // C++17
}

The memory cost of the merge phase is O(k) — one buffered element per open file — regardless of n. Production implementations add a second level of merging when k is large (e.g., merge groups of 16 runs to limit open file-descriptor count), but the algorithmic pattern is identical at each level.

`std::ranges::merge` Return Value

The in_in_out_result struct returned by std::ranges::merge carries three iterators: in1 (past-the-end of the first input), in2 (past-the-end of the second input), and out (past-the-end of the output). Capturing the return value avoids a separate std::distance or manual bookkeeping call when composing merges.

A practical use is chaining: the out iterator from the first merge becomes the starting point for the next merge without recomputing the output size. The in1 and in2 members also let callers verify that both input ranges were fully consumed — useful for defensive assertions in pipelines.

cpp

Godbolt

#include <algorithm>
#include <vector>
#include <string>
#include <iterator>
#include <cassert>

// C++20
// Merge three sorted name lists: first merge A+B, then merge result with C.
// Uses the out iterator from each merge as the starting point for the next.
std::vector<std::string> merge_three(std::vector<std::string> a,
                                     std::vector<std::string> b,
                                     std::vector<std::string> c) {
    std::vector<std::string> out;
    out.reserve(a.size() + b.size() + c.size());

    // --- First merge: A + B ---
    auto r1 = std::ranges::merge(a, b, std::back_inserter(out));  // C++20

    // Verify both input ranges were fully consumed.
    assert(r1.in1 == a.end());
    assert(r1.in2 == b.end());
    // r1.out now points to the position one past the last A+B element.

    // --- Second merge: (A+B result already in out) + C ---
    // Re-merge in place by capturing the current output size as the mid-point.
    const std::size_t ab_end = out.size();

    // Append C to out first, then inplace_merge the two halves.
    out.insert(out.end(), c.begin(), c.end());
    std::inplace_merge(out.begin(),
                       out.begin() + static_cast<std::ptrdiff_t>(ab_end),
                       out.end());  // C++98

    return out;
}

// Alternatively: chain two ranges::merge calls using the out iterator.
std::vector<std::string> merge_three_out_chain(std::vector<std::string> a,
                                               std::vector<std::string> b,
                                               std::vector<std::string> c) {
    // Allocate a temporary buffer for A+B, then merge that with C.
    std::vector<std::string> ab;
    ab.reserve(a.size() + b.size());

    auto r1 = std::ranges::merge(a, b, std::back_inserter(ab));  // C++20
    assert(r1.in1 == a.end() && r1.in2 == b.end());

    std::vector<std::string> out;
    out.reserve(ab.size() + c.size());

    auto r2 = std::ranges::merge(ab, c, std::back_inserter(out));  // C++20
    // r2.out is past-the-end of the final merged sequence —
    // useful as a starting iterator for a subsequent write or transform.
    assert(r2.in1 == ab.end() && r2.in2 == c.end());

    return out;
}

Inspecting in1 and in2 after the call is a lightweight correctness check: if either does not equal its sentinel, the merge was cut short (e.g., due to a size mismatch), which would indicate a bug in the caller's bookkeeping.

Performance: Out-of-Place vs In-Place

The choice between std::merge and std::inplace_merge involves a three-way trade-off between memory, time, and worst-case predictability.

std::merge into a pre-allocated buffer is purely memory-bandwidth limited: it reads n elements once and writes n elements once. For 1M 32-bit integers (~4 MB read + 4 MB write), this is approximately 8 ms on hardware with 2 GB/s effective memory bandwidth, and the cost is O(n) deterministically regardless of system state.

std::inplace_merge requests a temporary buffer internally. When the allocation succeeds, it performs the same read-write sequence as std::merge and runs in roughly the same ~8 ms. When the allocation fails (memory-constrained systems, huge arrays, or fragmented heap), the implementation falls back to an in-place algorithm with O(n log n) comparisons — for 1M integers this can rise to ~120 ms or more.

cpp

Godbolt

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

// C++11
// Microbenchmark-style comparison of merge vs inplace_merge.
// Run with -O2; timings are illustrative for 1M int on a 2020-era desktop.
void benchmark_merge_variants() {
    constexpr int N = 1'000'000;  // C++14
    std::vector<int> a(N / 2), b(N / 2);

    // Fill with sorted data.
    for (int i = 0; i < N / 2; ++i) { a[i] = 2 * i;     b[i] = 2 * i + 1; }

    // --- std::merge: always O(N), separate buffer ---
    {
        std::vector<int> out(N);  // pre-sized, no back_inserter overhead
        auto t0 = std::chrono::high_resolution_clock::now();

        std::merge(a.begin(), a.end(), b.begin(), b.end(), out.begin());  // C++98

        auto t1 = std::chrono::high_resolution_clock::now();
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0);
        std::cout << "std::merge:          " << ms.count() << " ms\n";
        // Typical: ~8 ms — bandwidth limited, no branching on heap state.
    }

    // --- std::inplace_merge: O(N) with allocation, O(N log N) without ---
    {
        std::vector<int> combined;
        combined.reserve(N);
        combined.insert(combined.end(), a.begin(), a.end());
        combined.insert(combined.end(), b.begin(), b.end());

        auto t0 = std::chrono::high_resolution_clock::now();

        std::inplace_merge(combined.begin(),
                           combined.begin() + N / 2,
                           combined.end());  // C++98

        auto t1 = std::chrono::high_resolution_clock::now();
        auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(t1 - t0);
        std::cout << "std::inplace_merge:  " << ms.count() << " ms\n";
        // Typical with allocation: ~8 ms.
        // Typical without (e.g. -DGLIBCXX_DEBUG or tight heap): ~120 ms.
    }
}

// Note on back_inserter overhead (assembly perspective):
// Using std::back_inserter instead of a pre-sized out.begin() introduces
// a branch + possible reallocation on every write.  With -O2, GCC/Clang
// cannot always hoist the capacity check out of the loop because the
// back_insert_iterator's operator= calls push_back, which can invalidate
// the vector's internal pointers.  Pre-sizing and using out.begin() lets
// the compiler emit a tight memcpy-style inner loop with SIMD stores.
// On Compiler Explorer (godbolt.org), compare the two forms with -O2 -march=native:
//   std::merge(..., out.begin())       — ~6 vmovdqu instructions per 32 bytes
//   std::merge(..., back_inserter(out)) — includes cmp+je branch each iteration

Prefer std::merge with a pre-sized output buffer for performance-critical paths. Reserve a.size() + b.size() and pass out.begin() rather than back_inserter to enable the compiler to generate tight SIMD store loops. The back-inserter form is convenient but measurably slower on large inputs.

Custom Allocator Usage

For small, bounded merges in hot paths — inner loops of a query engine, real-time audio processing, game tick updates — heap allocation for the output vector is unnecessary overhead. PMR (Polymorphic Memory Resources, C++17) lets you back a std::pmr::vector with a stack-allocated buffer, eliminating every malloc/free call during the merge.

The pattern is straightforward: declare a std::array<char, N> on the stack, wrap it in a monotonic_buffer_resource, construct a std::pmr::vector that references that resource, and call reserve before the merge. The monotonic_buffer_resource hands out memory in a bump-pointer fashion and never frees individual allocations — reset the resource as a whole when the result is no longer needed.

cpp

Godbolt

#include <algorithm>
#include <array>
#include <memory_resource>
#include <vector>
#include <iterator>

// C++17
// Merge two small sorted ranges with zero heap allocations.
// Template parameter MaxElems bounds the output size at compile time.
template<std::size_t MaxElems>
std::pmr::vector<int> merge_no_heap(const std::vector<int>& a,
                                    const std::vector<int>& b) {
    // Stack buffer sized for MaxElems integers plus pmr bookkeeping.
    // sizeof(int) * MaxElems is the data; add slack for alignment padding.
    static constexpr std::size_t BufBytes =
        sizeof(int) * MaxElems + 64;  // 64 bytes alignment headroom  // C++17

    std::array<char, BufBytes> buf;                                     // C++11
    std::pmr::monotonic_buffer_resource res{buf.data(), buf.size()};    // C++17

    std::pmr::vector<int> out{&res};                                    // C++17
    out.reserve(a.size() + b.size());
    // reserve() allocates once from the monotonic resource.
    // No subsequent allocation occurs during the merge.

    std::merge(a.begin(), a.end(),
               b.begin(), b.end(),
               std::back_inserter(out));  // C++98

    return out;
    // When 'out' is destroyed, pmr::vector calls the resource's deallocate —
    // a no-op for monotonic_buffer_resource.  The stack array is freed
    // automatically when the enclosing scope exits.
}

// Usage example:
void process_sorted_pairs() {
    std::vector<int> evens{0, 2, 4, 6, 8};
    std::vector<int> odds {1, 3, 5, 7, 9};

    // 10 elements max; stack buffer is ~104 bytes — no heap traffic.
    auto merged = merge_no_heap<16>(evens, odds);  // C++17
    // merged == {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
}

Use pmr::monotonic_buffer_resource to eliminate heap allocations when the merged output size is bounded at compile time. This technique is especially valuable in real-time or low-latency contexts where malloc latency is non-deterministic. If MaxElems is ever exceeded, the resource falls back to its upstream allocator (the default new/delete allocator) rather than crashing — a safe overflow behaviour worth documenting in caller contracts.