Nウェイマージのアルゴリズム

質問

2ウェイマージはMergesortアルゴリズムの一部として広く研究されています。 しかし、私はNウェイマージを実行することができる最良の方法を見つけることに興味があるのですか？

例えば、私が N ファイルがあり、それぞれ 100 万個の整数がソートされています。 それらを 1 億個のソートされた整数を持つ 1 つのファイルにマージする必要があります。

この問題のユースケースは、実際にはディスクベースの外部ソートであることに留意してください。したがって、実際のシナリオでは、メモリの制限もあります。したがって、一度に 2 つのファイルをマージする (99 回) という単純なアプローチではうまくいきません。各配列で利用可能なメモリの小さなスライディング ウィンドウしかないとします。

この N ウェイ マージに対する標準的なソリューションがすでに存在するかどうかはわかりません。 (ググってもあまりわかりませんでした) .

しかし、もし良いn-wayマージアルゴリズムがあれば、algo/linkを投稿してください。

時間の複雑さ。 ファイル数を大幅に増やすと ( N )を大幅に増やした場合、アルゴリズムの時間的複雑性にどのような影響を与えるでしょうか？

ご回答ありがとうございます。

どこにも聞かれたことはないのですが、これは面白いインタビューの質問になりそうな気がしました。そのためタグ付けしました。

どのように解決するのですか？

次のように考えてはどうでしょうか。

1. 優先キューを作成する
   
   
   
   
2. 各ファイルの繰り返し処理 f
   1. ペアをキューに入れる (nextNumberIn(f), f) 最初の値を優先キーとして
      
      
      
      
3. キューが空でない間
   1. キューを削除する (m, f) 待ち行列の
   2. 出力 m
   3. もし f 枯渇していない
      1. 待ち行列 (nextNumberIn(f), f)

優先キューへの要素の追加は対数時間で行えるので、項目 2 は O(N × log N) . whileループの（ほとんどすべての）反復は要素を追加するので、whileループ全体は O(M × log N) ここで M はソートする数値の総数です。

すべてのファイルが空でない数字の並びを持っていると仮定すると、次のようになります。 M > N となり、したがって、アルゴリズム全体は O(M × log N) .