在c ++中合并8个排序列表,我应该使用哪种算法

Question

我有8个排序列表,我需要合并到1个排序列表中.我不知道这样做的最好方法.我在考虑以下几点:

void merge_lists_inplace(list<int>& l1, const list<int>& l2)
{
    list<int>::iterator end_it = l1.end();
    --end_it;
    copy(l2.begin(), l2.end(), back_inserter(l1));
    ++end_it;
    inplace_merge(l1.begin(), end_it, l1.end());
}

list<int> merge_8_lists(list<int>[8] lists)
{
    merge_lists_inplace(lists[0], lists[1]);
    merge_lists_inplace(lists[2], lists[3]);
    merge_lists_inplace(lists[4], lists[5]);
    merge_lists_inplace(lists[6], lists[7]);

    merge_lists_inplace(lists[0], lists[2]);
    merge_lists_inplace(lists[4], lists[6]);

    merge_lists_inplace(lists[0], lists[4]);

    return lists[0];
}

但是最后担心排序会更好吗？

list<int> merge_8_lists(list<int>[8] lists)
{
    for (int i = 1; i < 8; ++i)
        copy(lists[i].begin(), lists[i].end(), back_inserter(lists[0]));        
    lists[0].sort();
    return lists[0];
}

旁注:我不关心列表是否被修改.

Answer 1

合并排序的合并阶段的简单扩展可以使用优先级队列(例如,堆)在O(n lg m)时间(其中n =项目总数和m =列表数)中执行此操作.伪代码:

Let P = a priority queue of the sorted lists, sorted by the smallest element in each list
Let O = an empty output list
While P is not empty:
  Let L = remove the minimum element from P
  Remove the first element from L and add it to O
  If L is not empty, add L to P

在C++中一个简单的(未经测试的!)具体实现:

#include <list>
#include <set>

template<typename T>
struct cmp_list {
    bool operator()(const std::list<T> *a, const std::list<T> *b) const {
        return a->front() < b->front();
    }
};

template<typename T>
void merge_sorted_lists(std::list<T> &output, std::list<std::list<T> > &input)
{
    // Use a std::set as our priority queue. This has the same complexity analysis as
    // a heap, but has a higher constant factor.
    // Implementing a min-heap is left as an exercise for the reader,
    // as is a non-mutating version
    std::set<std::list<T> *, cmp_list<T> > pq;

    for ( typename std::list<std::list<T> >::iterator it = input.begin();
            it != input.end(); it++)
    {
        if (it->empty())
            continue;
        pq.insert(&*it);
    }

    while (!pq.empty()) {
        std::list<T> *p = *pq.begin();
        pq.erase(pq.begin());

        output.push_back(p->front());
        p->pop_front();

        if (!p->empty())
            pq.insert(p);
    }
}