Multi-merge algorithm in C++
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);
    }
}