algorithm - 他のデータ構造と並べ替えをマージしますか?

Question

多くのテキストブックでは、ランダムアクセスの利点を考慮して、トップダウンのマージソートは配列で行われているようです。

他のデータ構造でマージソートを行う方法があるかどうか疑問に思っていますか? データがキューまたはスタックに格納されているとします。最大でも別の補助キュー/スタックを使用して、キュー/スタックでマージ ソートを実行できますか?

私の主な懸念は、ランダムアクセスがないため、この場合でもマージソートは O(n logn) 効率に達することができるでしょうか?

Answer 1

マージソートで配列を使用することのもう 1 つの利点は、巧妙な (しかし理解できない) アルゴリズムを作成すると、再帰呼び出しのレベル間で「スクラッチ」配列と「実際の」配列を切り替えることができることです。そのソルトに値するマージソートの実装では、「スクラッチ」配列を1回だけ割り当てますが、切り替え手法を使用すると、結果を最大1回移動するだけで済みます。

スタックとキューでは、基本的なデータ構造として配列を使用する可能性があります。リンクされたリストを使用できますが、アイテムにメモリを割り当てる必要があるため、push()andpop()またはenqueue()andの定数係数dequeue()が大きくなります。明らかに、@LearnedfromMistakeが示すように、スタックとキューを使用することは可能ですが、配列が基礎となるデータ構造として使用される可能性が高いことを考えると、そのようなアプローチの利点が何であるかは明確ではありません。