K路合并的最大K

Question

我正在尝试找出，K路归并排序的最大K是多少，或者是否有任何最大值。该算法的时间复杂度为O(nlogK)。我已经找了好几个小时了，还没找到。有没有人能把我链接到某篇文章上解释一下，或者告诉我有没有限制，为什么会有限制？另外，我想知道是否有推荐使用的K值，这是最有效的。

Answer 1

在内部(仅限内存)排序的情况下，无论K如何，对数据的操作总数都保持不变。假设x=n log2(n)。2路合并排序需要x次移动，最坏情况下x次比较，总共x+x= (2)x次操作。(从技术上讲，即使在最坏的情况下，也会有比x更少的比较，但x足够接近，可以理解这里的想法)。4路合并排序需要(1/2)x次移动和最坏情况(3/2)x次比较，因此仍然需要(1/2)x + (3/2)x = (2)x操作。如果比较比移动快，那么4路合并排序更快，如果移动比比较快，那么2路合并排序更快。还有像指针或索引这样的变量被保存在寄存器或堆栈中的问题，对于4路合并，你需要16个寄存器(比如64位模式下的X86 )。作为移动速度更快的示例，请考虑这样的情况:对指向对象的指针数组进行排序，只移动指针，但比较对象(这涉及到每个对象的指针取消引用)。

对于外部排序，在外部设备(磁盘驱动器，或在过去的一堆磁带驱动器)上创建的已排序块的内部排序可以是任何算法，K方式部分只是合并块。在外部排序传递的数量和足够大的K之间存在权衡，以便K路合并成为cpu限制而不是I/O限制。总时间是I/O时间加上超出I/O时间的任何cpu时间。大型数据文件的Gnu排序使用K= 16。K路合并是使用K元素最小堆完成的，其中每个堆条目对应于一个结构(或等效结构)，该结构保存块id、记录索引或指针、保留在内存中的块的记录数量、保留在块中的记录数量)。在初始创建具有K个条目的最小堆之后，堆的前端元素对应于具有K个条目中当前最小元素(假设升序排序)的结构。移动该元素以进行输出，从该块读取下一个元素，并更新堆以反映下一个元素在堆中放置前一个条目的位置。一旦到达块的末尾，合并就变成K-1合并，然后是K-2合并，直到只剩下1个块被复制。