マージソート：追加の配列コピーは必要ですか？

Question

「アルゴリズムの紹介」では、マージソートアルゴリズムは、呼ばれるヘルパー関数で実装されています MERGE(A, p, q, r) - これは、以前にソートされた2つのシーケンスをマージすることです。

この関数は、2つの追加配列を導入します 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