バッファでシリアルデータをソート

Question

データ長よりも短いバッファを使用してシリアル入力からデータをソートするアルゴリズムはありますか？

たとえば、100バイトのシリアルデータがあります。これは1回だけ読み取ることができ、40バイトのバッファは読み取り可能です。そしてソートされたバイトを出力する必要があります。

私はJavascriptでそれを必要としますが、一般的なアイデアは高く評価されます。

Answer 1

この種の並べ替えは、シングルパスではできません。

例を使用する：40バイトのバッファをいっぱいにしたので、次のバイトのためのスペースを確保するためにバイトを出力する必要があるとします。ソートされたデータを印刷するには、最初に最小バイトを印刷する必要があります。ただし、最小のバイトが読み込まれていない場合は、まだそれを印刷することはできません！

質問に最もよく適合するものはexternal sortingアルゴリズムで、メモリに収まらないデータを並べ替えるために複数のパスが必要です。つまり、処理パスの出力を保存できるペリフェラルがある場合は、O（ログ（N/M））パスでメモリより大きいデータをソートすることができます。ここで、Nは問題のサイズ、Mはあなたの記憶のサイズ。

外部ソート用の古典的なストレージペリフェラルはテープドライブです。しかし、（同じ種類の）ディスクドライブでも同じアルゴリズムが動作します。また、キャッシュ階層が深くなるにつれて、外部ソートの原則はメモリ内ソートでもより適切になります。cache-obliviousアルゴリズムを見てみてください。