基数排序通过将n个w位整数分成若干个logn\logn log n位的块，并在线性时间内对每个块进行排序，从而达到O(n w/logn)O(nw/\logn)O(n w/log n)时间。
1983年，Kirkpatrick和Reisch 1发表了一种算法，对此进行了改进。它实现的时间是n的下一个指数更小的因子：
正如最初发布的那样，该算法是确定性的，代价是使用大量的内存(Θ(2w/2))\Left(\theta(2^{w/2})\Right)(Θ(2w/2))。相反，将该思想与通用散列相结合以获得具有预期时间和线性空间的随机化算法更为实际。
我们将每个数字分成上半位和下半位(在我们的例子中，每个数字取4个十进制数字)。然后，我们将该数字作为长度为2的路径添加到trie中：在第一级，我们有更多有效位，在叶子中，我们有最低有效位。
请注意，在构建trie时，我们必须能够通过值查找第一级的节点，以避免重复它们。这就是散列(以及随机化)的用武之地。在树叶里，复制品是可以的。
我们获取除根和最小叶之外的所有节点，并递归地对它们进行排序。
有n片叶子。我们添加了一些1级节点，但跳过了相同数量的最小叶子，因此递归排序还对n个数字进行排序，每个数字的位数是n的一半。
使用在上一步中计算的节点的排序顺序，我们可以对所有边进行重新排序，从而使它们按排序顺序排列。
我们只需分离所有子节点(最少的叶子除外)，然后按排序顺序遍历所有节点，并将它们重新附加到其原始父节点。
现在，我们只需从左到右遍历Trie，并重新组合高位和低位，以获得最终排序的答案：
步骤1、2、4、5需要线性时间。步骤3要求递归排序长度为一半的数字。
如果我们将T(n，b)设为对n个b位数进行排序的时间，则得到递归公式：
T(n，b)=T(n，⌈b/2⌉)+O(N)\显示样式T(n，b)=T(n，⌈b/2\rceil)+O(N)T(n，b)=T(n，⌉b/2⌉)+O(N)。
一旦数字至多具有logn\logn log n位，我们就停止递归。在这一点上，我们可以通过计算每个值，在线性时间内进行排序。因此：
T(n，⌊logn⌋)=O(N)\DisplayStyle T(n，\lloor\logn\rFloor)=O(N)T(n，⌊log n⌋)=O(N)。
我们从每个w位开始，并希望分别记录n\logn log n位。每一级递归都会将位数减半，因此我们需要(w/loglogn)\log(w/\logn)logg(w/logn)级别。
柯克帕特里克、大卫和斯特凡·赖希。“随机访问计算机上整数排序的上限。”理论计算机科学(1983年)：263-276。↩