合并排序：是否需要额外的数组副本？
在“算法简介”中，合并排序算法是通过名为 MERGE(A, p, q, r) 的辅助函数实现的 - 该函数合并两个先前排序的序列。
此函数引入了两个附加数组 L 和 R 。
MERGE(A, p, q, r)
1 n1 ← q − p + 1
2 n2 ←r − q
3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
.....
通过“创建数组 L[1 . . n1 + 1] 和 R[1 . . n2 + 1]” 我理解为它们分配额外的内存。
是否可以重写这个函数，这样我就不需要额外的内存，并直接操作 A ？
In "Introduction to Algorithms" the merge sort algorithm is implemented with a helper function called MERGE(A, p, q, r) - that is merging two previously sorted sequences .
This function introduces two additional arrays L and R .
MERGE(A, p, q, r)
1 n1 ← q − p + 1
2 n2 ←r − q
3 create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
.....
By "create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]" I understand to allocate additional memory for both of them .
Is it possible to re-write this function, so that I won't need the additional memory, and to operate directly to A ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
当然。它称为就地合并排序。
维基百科说它很复杂 - 但事实并非总是如此。 有些并不像其他，如果您不关心运行时。
有一些变化，有些是稳定的，有些是不稳定的。有关示例，请参阅 NIST DIAGS 下的“实现”部分。
Sure. It is called in-place merge sort.
Wikipedia say it is complicated -- but it is not always true. Some are not as complicated as others, if you don't care about the run-time.
There are a few variance, some are stable, some are non-stable. See the "implementation" section under NIST DIAGS for some example.
是的，它被称为就地合并排序，但正如 Wikipedia 所说：
Yes, it's called in-place merge sort, but as Wikipedia puts it:
这是可能的。 http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper /mergesort_NJC.ps
That is possible. http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/mergesort_NJC.ps