「インプレース」反復LSD n-radixソート

Question

「インプレース」反復LSD n-radixソートを実装することは可能ですか？明確にするには：wikipedia atricle in-place MSD基数ソートを読んだことがあります。

カウントソートは、各ビンのサイズと開始インデックスを決定するために使用されます。

したがって、インデックスを格納するためには補助配列が必要ですが、それでも必要なものがあれば、それはまだインプレースアルゴリズムとみなされます（この配列はn-基数ソート）。また、再帰MSD基数ソートが実装されているthis answerも読んでいます。これには、n-radixソートの一般的な実装もありません。

Answer 1

はい。入力データを事実上いくつかのサイズのページに分割します（4KBはうまく機能します）。次に、データを消費したときにこれらのページを再利用します。あなたはしかし、いくつかの余分なメモリが必要になります - 最初のバケットのnページまで、次ページ・ポインタ（1ページに1つのポインタ）、3 * n個のポインタをhead_page/CURRENT_PAGE/current_write_ptr用バケット

あたりのアルゴ：

1. 空きページのリストに入れて、空きページのリストに入れます。
2. エントリをバケットに移動します。入力データのページ全体が処理されたら、このページを空きページのリストに追加します。バケットページ全体が満たされたら、このバケットページのリストに追加し、空きリストから新しいバケットページを割り当てます。あなたがあれば、バケットもちろん​​

のために、元の配列に、それに合わせて部分的に

移動データの周囲に充填されたこのリスト内の各bicketあたりのページのリスト、最後のページになってしまいます複数のLSDパスが必要な場合は、最後のパスを除いてステップ3をスキップし、ステップ2で作成したリストから直接各ソートパスを開始することができます。ただし、余分なページが必要になります。