algorithm - 更好的预排序 block 排序算法

Question

我有一个非常大的元素列表(几百万)，这些元素在本地以可变大小的 block 进行排序。

a b c b i h a j k l e f g a b l...

我预先知道每个 block 的大小、开始和结束位置。

[a b c] [b i h m] [a j k l] [e f g] [a] [b l] ...

有没有更快的方法来使用可以利用边界信息的算法对列表进行排序？

Answer 1

您要找的关键字是k-way/multiway merging :
您有 k 个单独的排序列表，并希望将它们合并为一个大小为 n 的列表。

有两种基本方法具有相似的渐近运行时特征，但在实践中的工作方式不同:

迭代2路合并

(概念上)构建一个以列表为叶的平衡二叉树，并迭代地将它们合并在一起，直到只剩下一个列表。这为您提供 log k 合并操作(树的高度)，其中每个合并操作都需要时间 n。
这基本上就是 rakwaht 和 schnaader 所描述的。

直接k-way合并

使用(二进制)堆或锦标赛树来存储尚未为每个 block 合并的最小元素。从此数据结构中删除最小元素会导致插入相应 block 中的下一个元素。因此，该算法的一个步骤需要 O(log k) 并重复 n 次，从而提供与迭代二进制合并相同的运行时间。

请注意，锦标赛树方法在实践中更有效，因为锦标赛树的遍历与二叉堆相比对数据的依赖性较低。

您也可以始终考虑介于这两种方法之间的解决方案，例如进行 16 路合并，这可能比上述两种“极端”方法中的一种更有效。

(迭代的)多路合并方法可能看起来更复杂，但是对于处理大量数据的应用程序(外部存储器 操作，将大部分数据存储在硬盘上)，这很复杂效率更高，因为需要的合并步骤少得多。