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

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

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

最佳答案

如果我们假设每个范围的大小大致相同并且总共有M个项目，那么std::sort将为您提供O(M log M)时间与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,

关于c++ - 如何在C++中合并多个排序范围？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54392071/