如何在c++中合并多个排序范围？

Question

std::merge在两个排序的范围上执行合并操作。我有N (>>2)个排序范围，我想将它们合并到一个排序范围中。

最明显的方法是使用std::merge N-1次。我想知道在C++ std库中是否有更好的算法。

Answer 1

如果我们假设每个范围的大小大致相同，并且总共有M个项目，那么对于简单的重复合并，std::sort将在O( merges )时间内给出正确的答案，而不是O(M^2)。我觉得正确的答案是将整个范围一分为二，然后在树中调用std::merge。如果我们假设每个范围的大小大致相同，并且它们是连续的，并且我们有一系列迭代器指向它们，我认为这是正确的方式：https://godbolt.org/z/GudjnM

// In-place merge multiple contiguous ranges.
// Could probably get better cache coherency
// if it merged lazily (depth-first traversal
// rather than breadth-first).
template <typename IterIter>
void multi_inplace_merge(const IterIter begbeg, IterIter endend) {
    while (std::distance(begbeg, endend) >= 3) { // There's work to do.
        auto output = begbeg; // We'll overwrite with the new ranges.
        auto it = begbeg;
        for (; it != endend && it + 1 != endend; it += 2) {
            if (it + 2 != endend) { // There's something to merge.
                std::inplace_merge(it[0], it[1], it[2]);
                *output = it[0];
                ++output;
                *output = it[2];
                ++output;
            } else {
                *output = it[1];
                ++output;           
            }
        }
        endend = output;
    }
}

例如

    std::vector<int> x = {1, 10, 100,   0, 9,  -1,5, 1000, 10000, 9999999};
    std::vector<decltype(x)::iterator> its = 
      {x.begin(), 
       x.begin() + 3, 
       x.begin() + 5, 
       x.end()};
    multi_inplace_merge(its.begin(), its.end());
    for (auto y : x) {
        std::cout << y << ", ";
    }
    std::cout << std::endl;

产生

-1, 0, 1, 5, 9, 10, 100, 1000, 10000, 9999999,