これはよくある質問です: 100 万個の 32 ビット整数をソートする最も効率的な (時間の複雑さの点で) 方法は何ですか? ほとんどの回答は、これらの数値のビット数は一定であると想定されているため、基数ソートを使用することが最善の方法の1つであることに同意しているようです。これは、CS の学生が非比較ベースの並べ替えを初めて学習するときによく行われる思考練習でもあります。ただし、詳細に (または少なくとも明確に) 説明されていないのは、アルゴリズムの基数 (またはバケットの数) を最適に選択する方法です。
この観察された回答では、バケットの基数/数の選択は経験的に行われ、32 ビット 100 万の整数に対して 2^8 であることが判明しました。その番号を選択するより良い方法があるかどうか疑問に思っていますか? 「Introduction to Algorithms」(p.198-199) では、Radix のランタイムは Big Theta(d(n+k)) (d=桁/パス、n=項目数、k=可能な値) である必要があると説明されています。さらに、n b ビットの数値と任意の正の整数 r <= b を指定すると、radix-sort は Big Theta((b/r)(n+2^r)) 時間で数値を並べ替えます。次に、「b>= floor(lg(n)) の場合、r ~= floor(lg(n)) を選択すると、一定の係数内で最適な時間が得られます...」。
しかし、観察された答えが示唆するように、 r=lg(1million)~=20 != 8 を選択した場合。
これは、本が示唆している「rの選択」アプローチを誤解している可能性が非常に高く、何かが欠けている（可能性が非常に高い）か、観察された答えが最適な値を選択しなかったことを示しています。
誰かが私のためにこれを片付けることができますか? 前もって感謝します。