一道经典C++编程题，排序k个排好序的std::list

1. 问题：

有k个已经排好序的std::list, 把它们合并成一个大的排好序的std::list.

例如有以下3个列表：

1->3->5

4->6

2->7

输出：1->2->3->4->5->6->7

2. 思路

本文尽量说明思考的过程，而不是直接给出结果。争取达到“授人以渔”的效果。

下面分析能想到的算法, 顺带分析时间复杂度，假设有k个列表，每个list长度为n：

1). 前两个直接使用std::list.merge合并，结果和第三个merge，再和第四个merge，直到最后一个。

Complexity

At most std::distance(begin(), end()) + std::distance(other.begin(), other.end()) - 1 comparisons.

所以一次合并的时间复杂度等于两个list的长度之和，故以上算法的时间复杂度为

 2n+3n+4n+...+kn = O(nk^2)

2). 可以看到上述算法时间复杂度与k的平方成正比，随着k的增长时间复杂度增长很快！k一旦上来算法的效率就很低了。想想k/2个list复杂度是多少？O(n(k/2)^2)=O(nk^2/4), 和另外一半k/2合并总时间复杂度O(nk^2/2)+O(nk/2+nk/2)=O(nk^2/2+nk),  当k稍大时+nk可以忽略几乎是原来的一半！只要nk^2/2>nk=>k>2分两组策略就更优。

      k/2还可以继续分成两个k/4, 根据以上公式效率也更高。所以最优策略是两个一组，两个一组合并成2n的list，再两个2n的一组合并成4n,...

       第一层：两个一组合并成2n   时间复杂度=（n+n）* k/2 = kn

       第二层： list长度为2n, 共合并k/4次   时间复杂度= （2n+2n）* k/4 = kn

       ....

        共log(k)层，所以此算法的总时间复杂度= O(nklog(k))

3). 还可以设置k个指针（迭代器）分别指向k个list的第一个元素，找出它们中最小的元素放入结果列表，把这个指针++指向下一个；再找出k个指针中最小的元素，放入结果列表，...,  直到k个指针都指向了各自的end。此算法每次只找出一个元素放入结果列表，需要kn次查找；总的效率完全取决于内层查找最小元素的效率，如何组织这k个指针是关键。

• 直接用list，按原始k个list的顺序。查找最小元素需要k-1次比较，O(k).
• 使用sorted list, 最小元素是第一个，插入新值最少1次比较，最差n-1次比较。平均O(k/2)
• 使用min-heap（priority queue - pq）. pop最小元素后需要立即组织heap，耗时O(log(k)), 插入新值也耗时O(log(k)). 平均O(2log(k)), 其实说大O时2可以省略。

故使用min-heap组织这k个指针比较好，总时间复杂度= O(nk*log(k)).

4). 对3也分组，效仿2。比如m个一组。时间复杂度推导直接上手稿吧，不爱画图。

3. 最优算法

综上所述，算法2）3）4）时间复杂度相当，但考虑到std::list.merge仅仅移动指针不拷贝数据，且它可以直接访问list的内部成员，效率应该更好一些。所以2）具有最优效率, 时间复杂度为O(nk*log(k))。考虑到算法3）中min-heap法的真正复杂度是kn*2log(k), 所以3）4）应该是2）的两倍左右耗时。

4. 实现（基于C++11）

/* [email protected]  20220426*/
template 
list mergeLL_group(list>& in_ll)  //算法2）
{
    auto ll = in_ll; //make a copy, so not modify the original in_ll
    typename list::size_type s = ll.size();
    if (s == 0)
    {
        return list();
    }
    if (s == 1)
        return ll.front();

    while(s>1){
        if(s%2==1) ll.push_back(list());
        typename list::size_type new_s = (s+1)/2;

        auto half2_first_iter = ll.begin();
        advance(half2_first_iter, new_s);
        list> last_half;
        last_half.splice(last_half.begin(), ll, half2_first_iter, ll.end()); //avoid copy, move second half to last_half
        typename list>::iterator half1_iter = ll.begin();
        typename list>::iterator half2_iter = last_half.begin();
        while(half1_iter!=ll.end()){
            half1_iter->merge(*half2_iter); //O(m+n)
            half1_iter++;
            half2_iter++;
        }
        s = new_s;
    }
    return ll.front();
}

    /* [email protected]  20220426*/
    template 
        list mergeSortedList(list> &lists)  //算法3）.pq
    {
        typedef typename list::iterator list_iter;
        typedef pair ptrs_value_type;

        auto cmp = [](const ptrs_value_type &p1, const ptrs_value_type &p2) -> bool
        { return *p1.first > *p2.first; };
        priority_queue, vector, decltype(cmp)> ptrs(cmp);

        for (auto &l : lists)
        {
            if (!l.empty())
            {
                ptrs.emplace(l.begin(), l.end());
            }
        }

        list res;

        while (!ptrs.empty())
        {
            // get the minimal iterator that ptrs points to
            auto cur_end = ptrs.top();
            ptrs.pop();
            res.push_back(*(cur_end.first));
            cur_end.first++;
            if (cur_end.first != cur_end.second)
            {
                ptrs.push(cur_end);
            }
        }
        return res;
    }

5. 测试验证

1）4）速度较慢，没测，主要比较了2）3）。

---crowd vs sparse-----
Test performance, (max,k,listsize)=(100,100,100):
                  solution3-pq:        753
          solution2_list.merge:        332
Test performance, (max,k,listsize)=(1000000,100,100):
                  solution3-pq:        780
          solution2_list.merge:        355
---crowd. k vs listsize
Test performance, (max,k,listsize)=(100,100,500):
                  solution3-pq:       3863
          solution2_list.merge:       1858
Test performance, (max,k,listsize)=(100,100,1000):
                  solution3-pq:       7792
          solution2_list.merge:       4027
Test performance, (max,k,listsize)=(100,500,100):
                  solution3-pq:       4697
          solution2_list.merge:       2268
Test performance, (max,k,listsize)=(100,1000,100):
                  solution3-pq:      10062
          solution2_list.merge:       5370
---sparse. k vs listsize
Test performance, (max,k,listsize)=(1000000,100,500):
                  solution3-pq:       3855
          solution2_list.merge:       2017
Test performance, (max,k,listsize)=(1000000,100,1000):
                  solution3-pq:       7790
          solution2_list.merge:       4638
Test performance, (max,k,listsize)=(1000000,500,100):
                  solution3-pq:       4620
          solution2_list.merge:       2451
Test performance, (max,k,listsize)=(1000000,1000,100):
                  solution3-pq:      10101
          solution2_list.merge:       5680