大きなデータセットにマージソートを実際に使用する方法

Question

大きなデータセットに対して実際にマージソートを使用するにはどうすればよいですか？

1.TXT

1 
2 
2 

2.txt

3 
4 
5 

3.txt

：

は、私は次のようなデータを持ついくつかのソートされたファイルを持っていると仮定します

1 
1 
1 

メモリ内のすべてのファイルの内容を同時に保持することはできないとします（各ファイルから2つの番号だけを保持できるとします）。

この場合、R-wayマージソートを使用できると聞きましたが、どうすれば実際にそれを行うことができるのか分かりません。

ご覧のとおり、最初の繰り返しは、私たちに次のようにソート順序与える：

1 1 1 2 3 4 

を、私たちは、出力ファイルにそれをフラッシュします。ただし、次の反復で1（3.txtファイルから）を再度取得するため、結果のシーケンス全体が間違っています！

Answer 1

ファイルのある変数と同じくらい多くの変数に1つの変数を1つのファイルに添付して開始します。各ステップで、3つの変数のうち最も低い値を見つけて、それを同じファイルから再度入力しながら出力にフラッシュします。

| 1.txt | 2.txt | 3.txt | 
| 1  | 3  | 1  | output 1 refill from file 1 
| 2  | 3  | 1  | output 1 refill from file 3 
| 2  | 3  | 1  | output 1 refill from file 3 
| 2  | 3  | 1  | output 1 refill from file 3 
| 2  | 3  | nil | output 2 refill from file 1 
| 2  | 3  | nil | output 2 refill from file 1 
| nil | 3  | nil | output 3 refill from file 2 
| nil | 4  | nil | output 4 refill from file 2 
| nil | 5  | nil | output 5 refill from file 2 
| nil | nil | nil | end 

Answer 2

I heard that I can use some kind of R-way merge sort in this case but I don't understand how can I actually do it.

Nウェイマージを説明するのはとても簡単です。すべてのファイルを開き、それぞれから最初の要素を取得し、ヒープに配置します。 アルゴリズムは次に、ヒープ（ポップ）から最小の要素を取り出し、出力バッファに書き込んだ後、この項目の元のファイルから次の要素を読み込みます。すべてのファイルが空になるまで繰り返します。