2n RAMでn^2要素をソートする方法

Question

2n個のRAMを使用してn^2要素をソートする方法を教えてください。 考えられるアプローチの1つは、サイズnのn個のアレイにそれぞれ分割することです。そして、n要素内でマージソートを行い、最後にn個の配列にサイズnのヒープを保持します。しかし、これは、1つの要素が配置されるたびに、私はディスクの読み込みを行い、n要素が完成するたびにディスク書き込みを行うことを意味します。 より良い提案はありますか？おかげさまで

Answer 1

これはできません。要素のためだけにn^2のメモリが必要です。

この明らかなメモリ消費を考慮しない場合は、ヒープソートなどのインプレースソートアルゴリズムの1つをお勧めします。 O（1）余分なスペースが必要です。

外部ストレージがカウントされず、内部ストレージのみがカウントされる外部ソートアルゴリズムを探している場合は、ボトムアップのmergesortを使用することをおすすめします。あなたはこれを、あなたが望むほどの量の内部メモリを消費するようにすることができます。約2nのメモリを消費し、部分的にソートされた各セットから常にn/2個の要素を読み込み、それらをn個の要素の別の配列にマージします。結果をディスクに書き戻します（できるだけ別のファイルに書き込むことをお勧めします）。

Answer 2

キャッシュ忘却型優先度キューの実装がある場合は、ディスクとメモリ階層の各レベルでメモリ転送の観点から最適な実行時間を達成するために使用できます（http://courses.csail.mit.edu/6.897/spring05/lec/lec23.pdf参照）。

それ以外の場合は、単純なコードを最初から書きたい場合は、mergesortのディスクベースの実装がうまくいくはずです。基本的に、 "左"と "右"の半分を最初に再帰的にソートし、2nメモリを使ってそれらをマージして、再帰的にソートされたサブアレイをディスクからバッファすることによって、配列の範囲をソートできます。単純な実装では、これは適切ではないため、ディスク上にアレイの2つのコピーを保管して前後にシャトルする必要があります。