Kウェイマージのための最大K

Question

私は、Kウェイマージソートのための最大Kと最大値があるかどうかを調べようとしています。 このアルゴリズムの時間複雑度はO（nlogK）です。私は運がない数時間それを探していました。誰かが、私がそれが説明されているいくつかの記事に私をリンクさせることができますか、いくつかの制限があり、それがなぜそうであるか教えてください？ また、使用することが推奨されるKの価値があるかどうか、それが最も効率的であるかどうかを知りたいと思います。

Answer 1

内部（メモリのみ）のソートの場合、データの操作の総数はKに関係なくほぼ同じです。x = n log2（n）とします。 2ウェイマージソートにはxの移動が必要であり、最悪の場合のxは合計x + x =（2）xの演算を比較します。 （技術的には、最悪の場合でもxが比較されるよりも少し小さいが、xはここでその考えを得るのに十分に近い）。 4ウェイマージソートでは、（1/2）x移動と最悪の場合（3/2）xが比較されるため、合計でも（1/2）x +（3/2）x =（2）x操作の合計が必要です。比較が移動より速い場合、4ウェイマージソートは高速です。移動が比較より速い場合、2ウェイマージソートは高速です。また、レジスタやスタックにポインタやインデックスなどの変数が残っているという問題もあります.4ウェイマージでは、64ビットモードでX86などの16個のレジスタが必要です。移動がより速い例として、オブジェクトへのポインタの配列がソートされ、ポインタのみが移動されるが、オブジェクトが比較される（各オブジェクトのポインタ逆参照を含む）場合を考える。

外部のソートの場合、外部デバイス（ディスクドライブ、または旧式のテープドライブ）に作成されたソートされたチャンクへの内部ソートはどのアルゴリズムでもかまいません.Kウェイパートはちょうどチャンクをマージします。外部ソートパスの数とKのマージがI/Oバウンドの代わりにCPUバインドになるように十分な大きさのKの間にはトレードオフがあります。合計時間はI/O時間+ I/O時間を超える任意のCPU時間です。大きなデータファイルのGnuソートでは、K = 16を使用します.Kウェイマージは、K要素の最小ヒープを使用して行われます。各ヒープエントリは、チャンクID、レコードインデックスまたはポインタ、メモリに残っているチャンクのレコード数、チャンクに残っているレコード数）。 Kエントリを持つ最小ヒープを最初に作成した後、ヒープの先頭の要素は、Kエントリの現在の最小要素（昇順のソートを想定）を持つ構造に対応します。その要素が移動されて出力され、次の要素がそのチャンクから読み込まれ、ヒープが更新されて、次の要素がヒープ内の先頭の要素の配置場所を反映します。チャンクの終わりに達すると、マージはK-1マージになり、次にK-2マージが行われ、コピーされるチャンクは1つだけ残されます。