external-sorting - k-wayマージによる外部ソートとクイックソート

Question

どちらの方がよいですか？1GBのメモリと100GBのファイルをソートするとします。

10 ウェイ マージの 1 つのインスタンスには次のものが必要です。

クイックソートには 100*7*2 (nlogn) 1GB のロードが必要ですか?

Answer 1

大規模なデータを処理する場合、マージ ソートは IO 効率が高くなります。

その理由は、クイック ソートが上から下へのアプローチであるためです。つまり、最初に 100 GB を処理する必要があり、50 GB * 2 を処理するよりも...大きなデータがある場合、データ全体をメモリに収めることは不可能です。

他の方法では、マージソートはボトムアップアプローチです。説明したように、データをメモリに収まる小さなバッチに分割し、それらをバッファにマージできます。

Answer 2

主なボトルネックは、実際にはハード ドライブの読み取りと書き込みです。ハード ドライブから各要素を 2 回読み取り、ハード ドライブから各要素を 2 回書き込みます。チャンクをソートするためにそれぞれ1回、次に多方向マージのためにそれぞれ1回。

対照的に、クイックソートは平均 O(log n) 回で各要素をハードドライブに読み書きします。