合并排序：是否需要附加阵列？

Question

在“算法简介”中，合并排序算法用辅助函数实现 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]
.....

经过 "create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]" 我了解为他们两个分配其他内存。

是否可以重写此功能，以便我不需要额外的内存并直接操作到A？

Answer 1

当然。它称为现场合并排序。

维基百科 说这很复杂 - 但并非总是如此。 一些 不像 其他, ， 如果你 不在乎运行时间.

有一些差异，有些是稳定的，有些是不稳定的。请参阅“实施”部分 nist diags 例如。

Answer 2

是的，这称为现场合并排序，但 维基百科 说：

就场分类是可能的（例如，使用列表而不是数组），但非常复杂，即使该算法在O（n log n）时间运行，也会在实践中几乎没有性能提高。 （Katajainen，Pasanen＆Teuhola 1996）

Answer 3

那是可能的。 http://www.diku.dk/hjemmesider/ansatte/jyrki/paper/mergesort_njc.ps