「インプレース」MSD基数ソートアルゴリズムを本当に混乱させています：
各ビンは、すべての桁が並べ替えに使用されるまで、次の桁を使用して再帰的に処理されます。
再帰は O(n) スタック スペースを意味するように思われるため、混乱しています。ここで、nは最長の文字列の長さ (ビット数) ですよね?
スタック オーバーフローを回避する唯一の方法はヒープ スペースを使用することのように思えますが、その場合、アルゴリズムは定義上、もはや「インプレース」ではありません。
では、インプレース MSD 基数ソートをインプレースで実行するにはどうすればよいでしょうか?
このアルゴリズムは、配列の両端からの 2 つの値を交換するため、インプレースです。例は次のとおりです。
{110,010,111,000,011}
0 ビンは左側に配置され、1 ビンは右側に配置されます。MSD から始めて、順を追って次のように並べ替えます。
{|110,010,111,000,010|}
{011|010,111,000|110}
{011,010|111,000|110}
{011,010,000||111,110}
これは、O(n) に簡略化されるこの例では O(3n) 時間で実行できます。必要な唯一の余分なメモリは、1 つの要素に十分な大きさのスワップ スペースです。