关于数组中的原地合并

Question

我看到了以下问题。

给定一个包含n个元素和一个整数k，其中k<n。已经排好序的元素{a₀...a_k}和 {a_k+1...a_n}。请提供一种时间复杂度为O(n)，空间复杂度为O(1)的算法进行排序。

在我看来，似乎无法以O(n)时间复杂度和O(1)空间复杂度完成此任务。实际上，这个问题似乎是在询问如何在原地执行归并排序中的合并步骤。如果可以这样做，为什么不将归并排序实现为这种方式呢？然而，我还没有完全相信自己的判断，需要一些意见。

- Sid

---

问题中是否特别指出归并排序？我知道可以原地进行归并排序，但不可能在O(n)时间内完成（至少我从未听说过）。 - jrista

不，它不是。我是在比喻合并步骤。它看起来很相似。 - Sid

如果您已经发布了问题的确切措辞，那么它似乎与归并排序无关。有一些排序算法对于预排序数组（即插入排序）是O（1）空间和O（n）原地排序的。归并排序不是其中之一，众所周知它不是其中之一，所以... - jrista

那么你会如何在O(n)时间内解决这个问题？ 有什么想法吗？也许你没有理解我的问题，这里有一个例子... {1,3,5,8}和{2,4,6,9}..你在暗示一个完全预排序的数组，但这不是我问题的情况。无论如何，对已经排序的数组进行排序是没有意义的。 - Sid

可能是重复的问题：如何使用O(n)时间和O(1)空间成本在原地合并两个已排序的整数数组 - Mark Byers

Answer 1

这篇文章似乎表明可以用O(lg^2 n)空间完成。我无法证明在常数空间内合并不可能，但我也不知道如何做到。

编辑： 查找参考资料，Knuth Vol 3 - Exercise 5.5.3说：“L. Trabb-Pardo的一种更为复杂的算法为这个问题提供了最佳答案：可以使用固定数量的索引变量，仅使用O(lg n)比特的辅助存储器，在O(n)时间内完成稳定合并和O(n lg n)时间内完成稳定排序。”

还有其他参考资料我没有阅读。感谢提供有趣的问题。

进一步编辑： 这篇文章声称，黄先生和兰斯顿先生的算法可以在O(m + n)的时间内合并两个大小为m和n的列表，所以你的问题的答案似乎是肯定的。不幸的是，我没有这篇文章的访问权限，所以我必须相信二手信息。我不确定如何将其与Knuth的声明相一致，即Trabb-Pardo算法是最优的。如果我的生命取决于此，我会选择Knuth。

我现在看到这个问题已经被问过很多次了，之前有人在Stack Overflow question上问过number次。我没有勇气标记它为重复内容。

黄炳熙和兰斯顿·A·M，《实用原地合并》，《ACM通讯》31 (1988) 348-352

- deinst

---

你说得对。我能够阅读这篇论文，因为我在大学里。虽然技术相当复杂，但似乎是可能的。感谢你的指引。 - Sid

您可以在CiteSeerX找到这篇论文。http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8523 - Daniel Brückner

@Daniel 谢谢。我的谷歌搜索技能需要提高。 - deinst

Answer 2

有几种算法可以实现这个，但都不是很容易直觉地理解。关键思想是使用数组的一部分作为缓冲区进行合并，然后使用该缓冲区作为辅助空间进行标准合并。如果您能将元素重新定位，使得缓冲区元素处于正确的位置，那就太好了。

如果您感兴趣，我在我的个人网站上写了一种实现其中一种算法。它基于黄和兰斯顿的论文“实用原地合并”。您可能需要阅读该论文以获得一些见解。

我还听说了一些很好的自适应算法，它们使用您选择的某个固定大小的缓冲区（如果您愿意，该缓冲区可以是O（1）），但是随着缓冲区大小的增加，比例也会变得优雅。我头脑中没有任何这些算法的信息，但我相信快速搜索“自适应合并”可能会找到一些东西。

- templatetypedef

Answer 3

不可能的，如果可以的话，我的工作会容易得多 :)

你有一个无法避免的O(log n)因素。你可以选择将其作为时间或空间，但唯一避免它的方法是不排序。使用O(log n)空间，您可以构建一个连续列表，跟踪未完全适合的元素的存储位置。通过递归，这可以使其适合于O(1)堆，但这只是使用O(log n)堆栈帧实现的。

以下是从1-9合并奇数和偶数的进度。请注意，您需要对记录由常量空间和线性交换的双重约束引起的顺序反转进行对数空间记账。

.     -
135792468
 .   -
135792468
  :  .-
125793468
   : .-
123795468
    #.:-
123495768
     :.-
123459768
      .:-
123456798
       .-
123456789
123456789

有一些微妙的边界条件，比二分查找更难正确处理，即使在这种（可能）形式下，也是一个糟糕的家庭作业问题；但是这是一个非常好的头脑锻炼。

更新 显然我错了，存在一种算法可以在O(n)时间和O(1)空间内实现。我已经下载了相关论文来让自己更清楚，因此撤回这个错误的答案。

- Recurse

---

链表是可能的。O(log n)来自其他地方。 - Joshua

我知道如何使用lg n的额外空间来完成它。但我不知道如何证明你不能做得更好，也就是说，需要O(lg n)的额外空间才能保持线性。 - deinst

@Joshua。说用链表实现这个并不公平，因为链表有O(n)额外的信息使它更容易--元素之间的指针。如果你能承受O(n)额外的空间，你可以用数组做得一样好。你分配一个新的结果数组，只需遍历两个原始数组，按顺序将项目复制出来即可。 - cape1232

@deinst 我并不觉得证明 lg n 是下限容易，但最终我确实证明了它对我来说是下限。那是多年前的事情，不幸的是我现在已经没有相关的资料了。然而，证明任何下限都高于 O(1) 相对而言还是相当简单的，这已足够满足我们在这里的目的了。 - Recurse