我试图找到一个算法来合并m个排序列表（共n个元素）在n log2 m runtme

Question

上面说了这一切。我真的不能想办法做到这一点，以及如何证明这一点。有任何想法吗？

Answer 1

将输入列表放入一个堆（又名优先队列）中，其中每个列表的优先级是其第一个元素。要获得输出列表的下一个元素，从堆上拉下顶部列表，将其第一个元素附加到输出列表中，从输入列表中移除该元素，并且（如果输入列表不是空的）将输入列表放回在堆中。重复，直到堆空。

有关更多详细信息，请参见this question and answer on Computer Science stackexchange。