外部メモリマージソート

Question

誰かが私に外部メモリmergesortに関する良い参照を指摘できますか？ Wikiページを読んでいますが、正確に理解するのに苦労しています。アニメーションが役立つかもしれませんが、私はそれを見つけることができないようです。

基本的に、私はあなたがディスクに一定数のブロックを持っていることを知っています、そしてあなたはメモリに一定数のブロックを適合させることができます。ディスクに32ブロック、メモリに4ブロックがあるとしましょう。最初のパスでは、一度に4ブロックをメモリに読み取り、メモリに並べ替えて、ディスクを書き戻します。したがって、この時点で、4ブロックの8つのソートランがあります。マージはどのように機能しますか？メモリには4つのブロックがあるので（出力用にもう1つあると仮定します）、これらの8つのランのうち4つを一度にマージし、次の4つのランをマージできるはずです。そして、最後のパスでは、全体をマージしたいと思います。しかし、毎回ディスクから各ブロックを読む必要はありませんか？それでは、これはどうして^2ソリューションにならないのでしょうか？

Answer 1

私は今それを手に入れていると思います。マージすると、ディスク上のすべてのブロックを読み取る必要があります（bと呼びましょう）が、b時間読む必要はありません。あなたはそれらをB log bを読むだけです。