Multi-merge algorithm in C++ As you know there is an algorithm in C++ standard library called std::merge, that merges two sorted ranges into another range. I try to write another merge (called multi_merge) that gets multiple sorted ranges (one or more), and merged them in one.
The code is as follows:

#include &lt;utility&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
#include &lt;iterator&gt;

template&lt;typename I&gt;
using range = std::pair&lt;I, I&gt;;

template&lt;typename I&gt;
struct is_empty_range {
    bool operator()(const range&lt;I&gt;&amp; x) const {
        return x.first == x.second;
    }
};

template&lt;typename I, typename Compare&gt;
struct range_compare {
    range_compare(Compare comp) : comp_{ comp } {}
    bool operator()(const range&lt;I&gt;&amp; x, const range&lt;I&gt;&amp; y) const {
        return comp_(*x.first, *y.first);
    }

    Compare comp_;
};

template&lt;typename I, typename O, typename Compare&gt;
O multi_merge(std::vector&lt;range&lt;I&gt;&gt; inputs, O output, Compare comp) {
    inputs.erase(std::remove_if(std::begin(inputs), std::end(inputs), is_empty_range&lt;I&gt;{}),
        std::end(inputs));

    if (inputs.empty())
        return output;

    while (inputs.size() != 1) {
        auto min = std::min_element(std::begin(inputs), std::end(inputs), range_compare&lt;I, Compare&gt;{comp});
        if (min-&gt;first != min-&gt;second) {
            *output = *min-&gt;first;
            ++min-&gt;first;
            ++output;
        }
        else {
            inputs.erase(min);
        }
    }

    return std::copy(inputs[0].first, inputs[0].second, output);
}

template&lt;typename I, typename O&gt;
O multi_merge(std::vector&lt;range&lt;I&gt;&gt; inputs, O output) {
    return multi_merge(inputs, output, std::less&lt;typename std::iterator_traits&lt;I&gt;::value_type&gt;{});
}


I want to know your opinions about this code, especially the way I'm passing list of ranges (a vector of pairs of iterators) to the algorithm. Do you recommend a more general way?

Here is a simple piece of code to test the algorithm:

#include &lt;numeric&gt;
#include &lt;iostream&gt;

int main() {
    constexpr size_t count = 10000;
    std::vector&lt;int&gt; v(count);
    std::iota(v.begin(), v.end(), 0);
    std::random_shuffle(v.begin(), v.end());

    using it_t = std::vector&lt;int&gt;::iterator;
    std::vector&lt;range&lt;it_t&gt;&gt; inputs;
    for (auto part = 0u; part &lt;= count - 1000; part += 1000)
        inputs.emplace_back(v.begin() + part, v.begin() + part + 1000);

    for (auto r : inputs)
        std::sort(r.first, r.second);

    std::vector&lt;int&gt; output;
    output.reserve(count);

    multi_merge(inputs, std::back_inserter(output));

    std::cout &lt;&lt; std::boolalpha &lt;&lt; "output size is correct: "
        &lt;&lt; (output.size() == count) &lt;&lt; '\n';
    std::cout &lt;&lt; std::boolalpha &lt;&lt; "output is sorted: "
        &lt;&lt; std::is_sorted(output.begin(), output.end()) &lt;&lt; '\n';
}


 Godbolt Link
Efficiency

The algorithm is suboptimal. Selecting a min is linear in the number of ranges. Arranging them in a priority queue would make it logarithmic.
Correctness

Testing for (min-&gt;first != min-&gt;second) is done too late. min-&gt;first == min-&gt;second means that the empty range participated in the comparison. Which in turn means that the end of that range was dereferenced. UB is imminent.

Since

inputs.erase(std::remove_if(std::begin(inputs), std::end(inputs), is_empty_range&lt;I&gt;{}),
std::end(inputs));


guarantees that there are no empty ranges at the beginning, I recommend to rewrite the loop as

while (inputs.size() != 1) {
    auto min = std::min_element(std::begin(inputs), std::end(inputs), range_compare&lt;I, Compare&gt;{comp});
    *output = *min-&gt;first;
    ++min-&gt;first;
    ++output;

    if (min-&gt;first != min-&gt;second) {
        inputs.erase(min);
    }
}