c - 合并排序列表

Question

我有四个排序列表，我想将它们合并到一个排序列表中。
最有效的方法是什么？如果实现可以并行完成，那将是一个加号。

Answer 1

这是合并排序的合并部分。

只需在每个列表的开头取四个元素中的最小值并将其转储到输出中。重复直到所有列表都为空。假设这min4是一个固定成本，那么这将是 O(N)。

如果您有更多信息（例如列表的范围），您可能可以稍微改进一下，但我认为这些不会影响渐近复杂度。