在CSLR第199页中，他们指出：
引理8.4：给定n个b位数字和任何正整数r <= b，如果RADIX-SORT使用的稳定排序采用O，则RADIX-SORT会以O（（b / r）（n + 2 ^ r））的时间正确地对这些数字进行排序（n + k）输入的时间，范围为0至k。
作为理解这一点的一个示例，下面是我认为是CSLR推理（并提出问题）的内容：
我们从n个32位数字开始（b = 32）。我们有n个数字，它们的取值范围为0到2 ^ 32-1。如果运行基数排序，则需要对数字进行一次遍历，其中counting-sort与变量k一起使用（代表范围为0到k其中n个数落下）等于2 ^ 32-1。计数排序为O（n + k），所以如果k >> n，对于n的可变大小，我们得到了非常差的运行时间。
我们现在要做的是将每个32位数字拆分为四个8位数字。这意味着r = 8，因此这四个数字现在的范围为0到2 ^ 8-1 =255。d = b / r = 32/8 = 4是n个数字中每个数字的位数。
我的第一个问题是：我们能否将数字256作为四个8位数字中每个数字的新底数？ 我们现在有四个以256为基数的数字吗？
现在，当我们使用基数排序时，我们必须执行四遍而不是一次（计数排序被使用四次）。每遍是O（n + k），但现在k是2 ^ 8-1 = 255而不是2 ^ 32-1。因此，总运行时间为O（4 *（n + 255）。
因此，当我们将初始数字拆分为较小的r位数字时，我们会增加基数排序遍数，但会减少计数排序中的值范围。似乎有一个使运行时间最小的最佳r。
第二个问题：第199页上的一段似乎认为存在这样一个r值，使得表达式O（（b / r）（n + 2 ^ r））最小。有人可以提供更好的解释吗？我无法解决这个问题。
对于给定的n和b值，我们希望选择r的值，其中r <=b，以最小化表达式（b / r）（n + 2 ^ r）。如果b <lg（n），则对于r<= b的任何值，我们都有（n + 2 ^ r）= O（n）。因此，选择r = b会产生（b / b）（n + 2 ^ b）的运行时间，这是渐近最优的。如果b> = lg（n），那么选择r = lg（n）可以在恒定因子内获得最佳时间，如下所示。选择r = lg（n）会产生O（bn / lg（n））的运行时间。当我们将r增加到lg（n）以上时，分子中2 ^ r项的增长速度快于分母中的r项，因此将r增加到lg（n）以上将产生运行时间Omega（bn / lg（n） ）。相反，如果将r减小到lg（n）以下，则b / r项增加，而n + 2 ^ r项保持在O（n）。
在MIT开放式课件上（第7章，课程注释），他们在其中的算法课程中显示的最小化略有不同：计数排序以O（n + b）进行，其中b是表示数字的基数。因此，如果n个数字在0到k的范围内，则每个数字都具有d =对数为b的k个数字，其中每个数字都是0到b-1之间的数字。所以b现在是CSLR前面示例中的k。Radix- sort执行d个计数排序，因此总运行时间为O（d（n + b））= O（（n + b）（k的对数b））。当b选择为n时，这被最小化。 这与以上关于同一主题的CSLR讨论有什么关系。*
在这里部分回答。第一个问题-256是基数，而32位整数中将有四个8位数字。该文章缺少的内容是，需要对数据进行一次读操作才能创建一个计数矩阵，然后将其转换为索引矩阵（或指针）。在这种情况下，矩阵为[4] [256]。创建矩阵后，需要进行4次读/写基数排序才能对数据集进行排序。
第二个问题-对于基于数学的解释，（b / r）（n + 2 ^ r）=（b（2 ^ r（r log（2）-1）-n））/ r ^ 2的导数。当导数== 0时出现最小值（或最大值），当2 ^ r（r log（2）-1）-n = 0时出现最小值。对于n == 2 ^ 20（约100万），r〜= 16.606232的结果为O（）〜=2212837。一些示例值和O（）：
r O 18 2330169 17 2220514 16 2228224 15 2306867 12 2807125 8 4195328
但是，由于缓存问题，r对n的最佳值变得更小。在我的系统（Intel 2600K，3.4ghz）上，对于n = 2 ^ 20，r = 8是最快的。在n = 2 ^ 24时，r = 10.67，使用3个字段10、11、11最快。在n = 2 ^ 26左右，r = 16最快。再次，由于缓存问题，性能没有很大差异，r = 8与r = 16相比，不到10％。
