我有一个很大的元素列表（几百万个），这些元素在本地按可变大小的块排序。
abcbihajklefgab l ...
我事先知道每个块的大小，开始和结束位置。
[abc] [bihm] [ajkl] [efg] [a] [bl] ...
有没有使用可以利用边界信息的算法对列表进行排序的更快方法？
您要查找的关键字是k向/多向合并：
您有k个单独的排序列表，并希望将它们合并为一个size列表n。
有两种基本方法可以工作，它们具有相似的渐近运行时特征，但在实践中却有不同的工作方式：
（从概念上）用列表作为叶子构建平衡的二叉树，并将它们迭代合并在一起，直到只剩下一个列表为止。这为您提供了log k合并操作（树的高度），其中每个合并操作都需要时间n。
这基本上就是rakwaht和schnaader所描述的。
使用（二进制）堆或锦标赛树来存储尚未为每个块合并的最小元素。从此数据结构中删除最小元素将导致插入相应块中的下一个元素。因此，该算法的一个步骤需要O(log k)重复进行n，因此与迭代二进制合并的运行时间相同。
请注意，锦标赛树方法在实践中更为有效，因为锦标赛树的遍历与二进制堆相比，数据依赖性较小。
您还可以始终考虑这两种方法之间的解决方案，例如进行16路合并，它可能比上面两种“极端”方法之一更有效。
（迭代的）多路合并方法可能看起来更复杂，但是对于处理大量数据的应用程序（将大部分数据存储在硬盘上的外部存储器操作），由于需要更少的合并步骤，因此效率更高。