algorithm - 余分なスペースまたはインプレースなしのマージソート

Question

重複の可能性:
マージソートアルゴリズムを使用してインプレースでソートする方法は?

通常、追加の配列を使用してマージソートを使用してソートしますが、余分なスペースを使用せずにこれを行うことは可能ですか?

これが可能であれば、マージソートはクイックソートよりも優れているでしょうか?

Answer 1

はい、インプレース マージ ソートを実行できます。これは、追加のメモリが必要ないという意味ではありません。再帰は依然として O(lg n ) スタック スペースを必要とするためです (クイックソートと同様)。

編集：カタジャイネンの論文を読んでから長い時間が経ちましたが、スペースの複雑さの主張には注意を払いませんでした。どうやら、マージソートはO(1) 余分なスペースで実行できます。

しかし、いいえ、これはすべて、その言葉で何を意味するかを指定しない限り、あるアルゴリズムが別のアルゴリズムよりも優れているという意味ではありません. ランダム化されたクイックソートは、2次になる可能性がありますが、入力に関係なく、予想される操作の数が少なくなります。データに対してどちらが「より適切に機能する」かは、データの統計からプログラムが実行されるハードウェアまでのさまざまな要因によって異なります。