例如，给定一个整数数组及其两个连续序列的开始位置，即“b1”和“b2”，此外还提供了位置“last”，该位置指示第二个序列的结束位置。从数组[b1]到数组[b2-1]和从数组[b2]到数组[last]都是分开的顺序，如何将它们合并到位使用 O(n) 时间和 O(1) 空间 cost?
Kronrod 的合并是第一个发布的算法来做到这一点。大致是这样的：
将数组的两个部分拆分为大小为 k=sqrt(n) 的块。使用块的第一个元素作为比较的基础对块进行排序。这可以通过选择排序在 sqrt(n)^2=O(n) 中完成。这里选择排序的关键属性是它每个块都有恒定的移动，因此只有 #comparisons 是正方形的。
此阶段之后，对于每个元素A[i]数组中最多有k-1其下方“错误排序”的元素，即位于以下位置的元素j<i这样A[j]>A[i]。这些（可能）位于其下方最近的来自其他合并部分的块中。请注意，该块的第一个元素（以及它下面的所有其他块）已经相对于A[i]因为块是按其第一个元素排序的。这就是第二阶段起作用的原因，即实现完全排序的数组：
现在将第一个块与第二个块合并，然后将第二个块与第三个块合并，依此类推，使用最后两个块作为合并输出的临时空间。这将打乱最后两个块的内容，但在最后阶段，它们（与前一个块一起）可以通过选择排序在 sqrt(n)^2=O(n) 时间内进行排序。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
