我正在寻找一种优雅，高性能的解决方案来解决以下问题。

有256个链接列表。

• 每个列表包含相同类型的对象，该对象除其他外还包含用于定义排序顺序的整数。
• 所有列表中的所有数字都是唯一的
• 每个单独的列表按这些数字升序排列

如何从256个原始链接列表中的所有对象中创建一个单个的升序列表？我不希望强行使用它，并且还有其他一些想法，但这似乎是有一个标准的，最佳的解决方案的问题之一。

解决方案

我们可以使用优先级队列，该队列包含256个链表中每个链表的最顶层。此最顶层的项目是计划插入到结果列表中的项目。这样，我们可以只从优先级队列中取出最小的元素，将其插入到结果队列中，然后将其下一个元素插入优先级队列中：

# Preprocessing:
result = list.new()
queue = priority_queue.new()

foreach (list in lists):
    queue.push(list.first())

# Main loop:
while (not queue.empty()):
    node = queue.pop()
    result.insert(node)
    if (node.next() != null):
        queue.push(node.next())

如果单个列表已经排序，则它是合并算法的直接应用。简而言之：比较所有磁头并选择最小的磁头，将其从列表中删除，然后推入输出列表。重复直到所有源列表都为空。

编辑：Konrad使用优先级队列(堆)是一种更为优雅且可扩展的解决方案，但可能有256个输入列表太少，因此简单比较可能会更快。

只需将每个列表与其上方的列表128合并即可。 (产生128个列表)
然后将每个列表与其上方的列表64合并。 (结果为64个列表)
然后将每个列表与其上方的列表32合并。 (结果为32个列表)
然后将每个列表与其上方的列表16合并。 (得出16个列表)
然后将每个列表与其上方的列表8合并。 (得出8个列表)
然后将每个列表与其上方的列表4合并。 (得出4个列表)
然后将每个列表与其上方的列表2合并。 (产生2个列表)
然后将每个列表与其上方的列表1合并。 (结果为1个列表)
(我们可以在上面使用循环)。

我们没有说这些列表有多长，但是我想它们都同时放在RAM中。我要尝试的第一件事是将它们全部添加在一起，并调用环境的内置排序例程，然后看看是否可以提供令人满意的性能。它很容易实现，并且不需要花费很长时间进行测试。如果那不能给出令人满意的性能，我将使用Konrad Rudolph给出的优先级队列合并。