異なる方法でマージソートアルゴリズムを実装したい

Question

マージソートは、リストを最小単位（1要素）に分割し、各要素を隣接するリストと比較して、隣接する2つのリストを並べ替えてマージします。最後に、すべての要素がソートされマージされます。 私は、リストを2つの要素の最小単位に分割し、ソートしてマージするような方法でマージソートアルゴリズムを実装したいと考えています。 ？ 私はそれをどのように実装できますか？

MERGEソート（A、P、R）

1. P < R //は、ベースケース
2. を確認した場合、Q = FLOORの[（P + R）/ 2] //分割ステップ
3. MERGE（A、p、q）//ステップを征服する。
4. MERGE（A、q + 1、r）//ステップを征服する。
5. MERGE（A、p、q、r）//ステップを征服する。

何かp < r + 1のようなものです。

Answer 1

私はこれまでこれを聞いたことがあります。ここに2つのバリエーションがあります。

バリエーション1：各ペアをソートしてリストを表示します。次に、リストの各ペアのペアをマージします。次に、4対の各対など。リスト全体をマージしたら、完了です。

バリエーション2：ソートされた配列のスタックがあります。各要素は下の配列にマージしてカスケードしますが、1つだけになるまでマージするか、上から2番目の要素は上よりも大きくなります。最後の要素が追加されたら、配列をマージして折り畳みます。

私がバリエーション2を使用したのは、非常に大量のデータが流入したケースでした。ソートされた配列の最初の数個のスタックをメモリに保存し、後でディスクに保存しました。これは、参照の良い局所性、およびディスクの効率的な使用につながります。 （なぜ私は棚番以外のソリューションを使用しなかったのかと聞いていますが、私が入ってきたデータセットは、それを処理しなければならなかったディスクよりも大きかったし、そこにロジックを組み込むカスタムがありました。