关于数组中的就地合并 [英] Regarding in-place merge in an array

问题描述

我遇到了以下问题.

给定一个 n 元素和一个整数 k 的数组，其中 k n.元素 {a₀...a_k} 和{a_k+1...a_n} 已经排序.给出一个在 O(n) 时间和 O(1) 空间内排序的算法.

Given an array of n elements and an integer k where k < n. Elements {a₀...a_k} and {a_k+1...a_n} are already sorted. Give an algorithm to sort in O(n) time and O(1) space.

在我看来，它不能在 O(n) 时间和 O(1) 空间内完成.问题似乎真的是在询问如何进行合并排序的合并步骤，但就地.如果可能，合并排序不会以这种方式实现吗?我无法说服自己，需要一些意见.

It does not seem to me like it can be done in O(n) time and O(1) space. The problem really seems to be asking how to do the merge step of mergesort but in-place. If it was possible, wouldn't mergesort be implemented that way? I am unable to convince myself though and need some opinion.

推荐答案

这 似乎表明可以在 O(lg^2 n) 空间中进行.我看不到如何证明在恒定空间中不可能合并，但我也看不到如何做到.

This seems to indicate that it is possible to do in O(lg^2 n) space. I cannot see how to prove that it is impossible to merge in constant space, but I cannot see how to do it either.

追逐参考文献，Knuth Vol 3 - 练习 5.5.3 说L. Trabb-Pardo 的一个相当复杂的算法为这个问题提供了最好的答案:可以在 O(n) 时间内进行稳定合并，并在O(n lg n) 时间，对于固定数量的索引变量，仅使用 O(lg n) 位的辅助存储器.

Chasing references, Knuth Vol 3 - Exercise 5.5.3 says "A considerably more complicated algorithm of L. Trabb-Pardo provides the best possible answer to this problem: It is possible to do stable merging in O(n) time and stable sorting in O(n lg n) time, using only O(lg n) bits of auxiliary memory for a fixed number of index variables.

更多参考资料，我还没有读过.感谢您提出一个有趣的问题.

More references that I have not read. Thanks for an interesting problem.

进一步这篇文章声称 Huang 和 Langston 的文章有一个算法，可以在 O(m + n) 时间内合并大小为 m 和 n 的两个列表，因此您的问题的答案似乎是肯定的.不幸的是，我无法访问这篇文章，所以我必须相信二手信息.我不确定如何将这与 Knuth 的声明相协调，即 Trabb-Pardo 算法是最佳的.如果我的生活取决于它，我会和 Knuth 一起去.

Further edit: This article claims that the article by Huang and Langston have an algorithm that merges two lists of size m and n in time O(m + n), so the answer to your question would seem to be yes. Unfortunately I do not have access to the article, so I must trust the second hand information. I'm not sure how to reconcile this with Knuth's pronouncement that the Trabb-Pardo algorithm is optimal. If my life depended on it, I'd go with Knuth.

我现在看到这个问题和之前的 Stack Overflow 一样 问题 a 次数 次.我不忍心将其标记为重复.

I now see that this had been asked as and earlier Stack Overflow question a number of times. I don't have the heart to flag it as a duplicate.

黄 B.-C.和 Langston M. A.，实用就地合并，Comm.ACM 31 (1988) 348-352

Huang B.-C. and Langston M. A., Practical in-place merging, Comm. ACM 31 (1988) 348-352

这篇关于关于数组中的就地合并的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！