マルチウェイマージと2ウェイマージ

Question

externally merge sort大きなファイルを分割して小さなファイルに分割し、それらを並べ替えて大きなソートファイルにマージします。

マージするときに、2ウェイマージパスを多数、または1つのマルチウェイマージを行うことができます。

どのアプローチが優れているのだろうか？なぜ？

Answer 1

一般に、1つのマルチウェイマージが優れています。考えてみましょう三つの小さなファイル：

a1 
a2 
a3 

と

b1 
b2 
b3 

し、最終的に

c1 
c2 
c3 

あなたはaとbとのマージを行う場合には、我々は、（例えば）

が残っています

a1 
b1 
a2 
b2 
b3 
a3 

および

c1 
c2 
c3 

最終マージソートされたリストを作成しますが、この最後のマージでは、我々は再びaとbアイテムを訪問する必要がどのように気づくでしょう。カスケーディングの双方向マージでは無駄です。この再統合です。

代わりにできるのは、単一のマルチウェイマージです。しかし、あなたはそれをどうするか注意してください。具体的には、各カーソルをスキャンして最小値を持つものを調べる単純なダブルループを避けてください。代わりに、min-heapを使用してください。これにより、複雑さはO(n log n)に戻されます。