例如，给定一个整数数组及其两个连续序列的起始位置，即'b1'和'b2'，还提供位置'last'，表示第二个序列的结束位置。从数组[b1] 到数组[b2-1] 和从数组[b2] 到数组[last] 都是分别按顺序排列的，如何使用O(n) 时间和O(1) 空间将它们合并到位 成本？
最佳答案
Kronrod 的合并是第一个发布的这样做的算法。大致是这样的:
将数组的两个部分拆分为大小为 k=sqrt(n) 的 block 。使用第一个元素作为比较的基础对 block 进行排序。这可以通过选择排序在 sqrt(n)^2=O(n) 中完成。这里选择排序的关键属性是它在每个 block 中有恒定的移动，所以只有#comparisons 是正方形。
在这个阶段之后，对于数组中的每个元素A[i]，它下面最多有k-1个元素“错误排序”，即位于定位 j<i 使得 A[j]>A[i]。这些(可能)位于它下方最近的来自其他合并部分的 block 中。请注意， block 的第一个元素(以及它下面的所有其他 block )已经相对于 A[i] 正确排序，因为 block 是根据它们的第一个元素排序的。这就是第二阶段起作用的原因，即实现完全排序的数组:
现在将第一个 block 与第二个 block 合并，然后将第二个 block 与第三个 block 合并，以此类推，使用最后两个 block 作为合并输出的临时空间。这将打乱最后两个 block 的内容，但在最后阶段，它们(连同前面的 block )可以在 sqrt(n)^2=O(n) 时间内通过选择排序进行排序。
关于algorithm - 如何使用 O(n) 时间和 O(1) 空间成本就地合并两个排序的整数数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2126219/