在「算法簡介」中,合併排序算法使用名爲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?
另請參閱此問題:http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm – 2010-11-29 14:59:21