Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::merge — stable merging of sorted ranges

std::merge from <algorithm> copies two sorted ranges into a separate output range. It preserves duplicates and stability, and returns an iterator one past the last element written.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>
std::merge(first1, last1, first2, last2, result);
std::merge(first1, last1, first2, last2, result, comp);

std::merge merges [first1, last1) and [first2, last2), writing every element starting at result. Both inputs must already be sorted using the same ordering: ascending by default, or the ordering specified by comp. The comparator must define a strict weak ordering. Unsorted inputs violate the algorithm's preconditions; the function does not sort the inputs first.

Merging is stable: it preserves element order within each input, and elements with equivalent keys from the first range precede those from the second. Equivalence means that neither comp(a, b) nor comp(b, a) is true. Duplicates remain in the output.

The output range must not overlap either input range. Provide space for the sum of their lengths, or use an appropriate insertion iterator. Calling only reserve() on a vector does not create elements writable through begin(). The returned iterator points one past the last element written.

For the overloads discussed here, without an execution policy, work is linear in the total element count N, with at most N - 1 comparisons when N > 0. Do not confuse this function with std::inplace_merge, which merges two adjacent sorted subranges within the same range. The example uses C++23-compatible syntax; the cited working draft is updated and may also include later extensions.

Examples

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    const std::array<int, 3> a{1, 3, 5};
    const std::array<int, 3> b{2, 3, 6};
    std::array<int, 6> result{};

    const auto end = std::merge(a.begin(), a.end(),
                                b.begin(), b.end(), result.begin());

    for (auto it = result.begin(); it != end; ++it) {
        if (it != result.begin()) {
            std::cout << ' ';
        }
        std::cout << *it;
    }
    std::cout << '\n';
}

Result

1 2 3 3 5 6

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources