我遇到了以下问题。
给定一个 n个 元素的数组和一个整数 k ，其中 k < n 。元素{ a 0 … a k }和{ a k +1 … a n }已经排序。给出一种在O（ n ）时间和O（1）空间中排序的算法。
在我看来，这似乎不能在O（ n ）时间和O（1）空间中完成。问题实际上似乎是在询问如何执行mergesort的合并步骤，但是是就地进行的。如果有可能，是否可以通过这种方式实现mergesort？我无法说服自己，需要一些意见。
这似乎表明可以在O（lg ^ 2 n）空间中进行操作。我看不到如何证明不可能在恒定空间中合并，但是我也看不到如何做到这一点。
编辑：追随参考，Knuth第3卷-练习5.5.3说：“ L。Trabb- Pardo的相当复杂的算法为该问题提供了最佳的答案：可以在O（n）时间进行稳定合并，并且可以进行稳定合并以O（n lg n）的时间排序，仅使用辅助存储器的O（lg n）位获取固定数量的索引变量。
我还没有阅读更多参考。感谢您提出一个有趣的问题。
进一步编辑：本文声称Huang和Langston的文章有一种算法，可以在O（m + n）的时间内合并大小为m和n的两个列表，因此您的问题的答案似乎是肯定的。不幸的是，我无权访问该文章，因此我必须信任二手信息。我不确定如何与Knuth的Trabb- Pardo算法是最佳的声明相协调。如果我的生活有赖于此，我会选择Knuth。
我现在看到这个问题已经被问过了，并且之前的堆栈溢出问题已经被问过很多次了。我不愿意将其标记为重复项。
黄BC 和Langston MA，实用就地合并，Comm。ACM 31（1988）348-352
