合并排序：是否需要额外的阵列副本？

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

当然。它被称为就地合并排序。

Wikipedia说这是复杂的 - 但它并不总是如此。 Some不像others那么复杂，如果你don't care about the run-time。

有几个方差，有些是稳定的，有些是不稳定的。例如，请参阅NIST DIAGS下的“实施”部分。

Answer 2

是的，这就是所谓的就地合并排序，但Wikipedia所言：

排序就地是可能的（例如，使用列表而不是数组），但非常复杂，并会提供小即使算法在O（n log n）时间内运行，在实践中性能也会有所提高。 （Katajainen，Pasanen & Teuhola 1996）

Answer 3

这是可能的。 http://www.diku.dk/hjemmesider/ansatte/jyrki/Paper/mergesort_NJC.ps