合并已排序的n个列表

您可以使用 priority queu E(基于二进制堆)。

用对填充队列 (current element of list or its index; list id) 是的。

At every step: 
   extract pair with min element from queue
   add value to result
   get the next element of the same list (if possible)
   insert new pair into queue again

相对于可用内存,您的列表有多大?
寻找有用的线索 wiki external sorting page

基本方法应该是创建一个最小大小的堆(n),其中n是从大列表中分区排序的列表数。 二进制堆的每个节点都应该表示为index/sorted_list_number和value。 最小堆的顶部节点将指向大列表的最小值,索引将指向排序列表的来源,现在从最小堆弹出的顶部将其值添加到大列表中,并将弹出的索引列表中的新值添加到堆中,然后再次进行堆修复。 重复直到节点完成,当一个/多个列表在进程中变空时,还要注意heapsize。

因为问题是您的列表大于内存,所以我认为外部排序是解决方案:

https://en.wikipedia.org/wiki/External_sorting

1. 假设我们有n个主内存块,我们可以加载两个列表中的n-1个块。使用剩余的一个块作为输出缓冲区

2. 通过比较前面的元素来执行通常的合并,从而合并两个列表。将结果输出到输出缓冲区。

3. 当缓冲区已满时,将输出写回辅助内存。

4. 重复这些步骤,直到合并所有列表。