あなたが試みていることは、外部ソートと呼ばれます。各パーティションは、それ自体でソートされます。次に、すべてのパーティションをマージして、最終的なソート済みリストを作成する必要があります。上位のいくつかのアイテムのみを探している場合は、マージを早期に終了できます。
外部マージ用の既存のソリューション matlab ソリューションがいくつかあるようです。mathworks のファイル交換サイトへのリンクは次のとおりです。
更新: リンクしたコードは、matlab での実行方法を示しています。具体的には、ここのコード: http://www.mathworks.com/matlabcentral/fileexchange/29306-external-merge-sort/content/ext_merge/extmerge.mは、マージする必要があるファイルのリストを取得し、最終的にそれらをマージします1 つのファイルに。
元の問題ステートメントでは、X1 から XK までの K 個のファイルがあると述べました。外部ソートは、最初にこれらのファイルをソートしてから、それらを 1 つのファイルにマージします。簡単な実装では、次のような疑似コードを使用します。
// external merge-sort algorithm
For each file F in (X1 ... XK)
Read file F into memory array R
Sort R
Overwrite file F with sorted data from R
Clear array R in memory
For N = K-1 down to 1
in-order merge file XN+1 and XN into file X'
erase file XN+1 and XN
rename file X' as XN
最初のフェーズはソートであることがわかります。各ファイルをメモリに読み込み、並べ替え、書き戻します。これは I/O ですが、効率的です。うまくいけば、できるだけ多くのメモリを使用して、できるだけ多くのメモリをソートできるようにしています。最初のループの終わりには、K 個のファイルがあり、それぞれが独自の値のドメイン内でソートされています。
K 個のファイルがソートされた場合、次のステップはそれらをマージすることです。2 つのファイルをマージしてもメモリは消費されませんが、大量の I/O が発生します。2 つのファイルのマージは次のようになります。L と R という名前の 2 つのファイルがあれば、それらを O にマージできます。
// merge two files algorithm
Get value LV from L
Get value RV from R
While L is not EOF AND R is not EOF
if ( LV <= RV )
write LV into O
get value LV from L
else
write RV into O
get value RV from R
While L is not EOF
get LV from L
write LV into O
While R is not EOF
get RV from R
write RV into O
マージソートの 2 番目のループは、2 つのファイル N+1 と N を 1 つのファイル N にマージします。各ファイルをループしてマージします。これは大量のデータの読み取りと再書き込みを行いますが、ループ内で複数のファイルを処理することにより、それよりも少し効率的になります。しかし、私が書いたようにうまくいきます。