ポリフェーズマージソート - フェーズの数は何ですか？

Question

大きな数字セットを外部でソートする必要があるとします。

1. 4本のテープ：2本の入力テープ、2出力
2. 3本のテープ：2、1アウト

ケース1：

我々は2例を調べたいです

kの実行から始めて、それらの実行を2つの入力テープ（下の写真の左側）にコピーし、入力テープから2つの異なる実行を取る各繰り返しをマージします（そしてソート）し、1回の反復では最初の出力テープに保存し、次の反復では2番目のテープに保存します。次に出力テープを入力テープで切り替えて、手順を繰り返します。だから我々が持っているとすれば、n=10^6要素とk=1000が実行された後、最初の段階の実行後には、2000、3番目の後に4000などとなります。したがって、相の総数はceil(log_2(n))です。

ケース2：最良の複雑さに

は、フェーズ数がposition of Fibonacci’s number in the Fibonacci’s sequence minus twoである、すなわち実行の我々の最初の数はk=34および34は、フィボナッチ数列における第九の数である場合には、それから7つのフェーズがあります。

しかし...実行の私達の数はフィボナッチ数でない場合、それはありません取得するためにダミーの実行とテープパッドに必要です。フィボナッチ数までのランの

は最後に、私の質問は：実行の数がフィボナッチ数でない場合、シーケンスをソートするために必要な相の平均の場合の数は何である

？

Answer 1

実行回数がフィボナッチ数でない場合のフェーズ数は何ですか？

実行カウントが理想的な数値でない場合、並べ替えは1つの余分なフェーズをとり、実行カウントを次の理想的な数値に丸めます。ダミー・ランはテープ上のスペースを占有する必要はありませんが、非理想的なディストリビューションのフェーズでは、複数のテープのデータの最後に到達するコードを処理する必要があります。

---

元の質問に記載されている情報に関するいくつかの注意事項：

4テープの例では、バランスの取れた2ウェイマージソートを示しています。ポリフェーズマージソートの場合、フェーズごとに1つの出力テープしかありません。 4台のテープドライブでは、初期設定で3台のドライブ間で実行が分配されるため、最初の配布後は常に3入力テープ、1出力テープです。

フィボナッチ数は、3つのテープシナリオにのみ適用されます。 4つ以上のテープのシナリオでは、シーケンスは最終フェーズで開始して後方に作業することで最も簡単に生成されます。4つのテープで31回実行した場合、最終実行回数は{1,0,0,0}、後方に作用する です：{0,1,1,1}、{1,0,2,2}、{3,2 、0,4}、{7,6,4,0}、{0,13,11,7}である。

ランサイズは、以前のさまざまなサイズのランをマージした結果として増加します。実行サイズは1要素、31ラン、4テープとする。初期分布後、ランカウント：ランサイズは{0：0,13：1,11：1,7：1}です。第1段階：{7：3,6：1,4：1,0：0}。第2段階：{3：3,2：1,0：0,4：5}。第3段階{1：3,0：0,2：9,2：5}。第4段階：{0：0,1：17,1：9,1：5}。第5段階および最終段階{1：31,0：0,0：0,0：0}。

実行サイズの追跡は複雑になる可能性があるため、テープの単純な解決策は、実行の終了を示す単一のファイルマークと、データの終了を示すダブルファイルマークを使用することです。

Wikiには、ポリフェーズマージソートに関する記事があります。

https://en.wikipedia.org/wiki/Polyphase_merge_sort

---

総実行回数が予め分かっている場合は、初期分布が理想的な数の実行カウントを取得するために、最初のマージ操作を含めることができますが、今、実行サイズは初期に起因して変わりますマージ操作を実行するので、各テープは実行サイズが混在することになります。ここでも、ファイルマークを使用して実行の終了を示すと、メモリ内の実行サイズを追跡する必要がなくなります。

ポリフェーズマージソートは、3つのスタックを使用してソートを行う最速の方法です。