在例4-11的sortPointers函数中，输入中的每一个元素根据提供的散列函数，被插入到相应的桶中，花费是线性时间O(n)。桶中的元素并不是有序的，但是由于仔细设计的散列函数，我们知道，如果i＜j，在桶bi中的所有的元素都小于bj中的所有元素。
随着值从桶中抽取出来并且写回到输入数组，当一个桶包含多个元素的时候就要使用插入排序。对于表现出O(n)性能的桶排序，我们需要保证排序每个桶所花费的总时间为O(n)。我们定义ni是分到桶bi的元素数目。我们能够将ni看做随机变（使用统计理论）。现在考虑ni的期望值E[ni]。输入中的每一个元素插入到一个给定的桶中的概率为1/p，因为每个元素的值是从[0,1)之间均匀抽取的。因此E[ni]=n*p=n*(1/n)=1，方差Var[ni]=n*p*(1-p)=(1-1/n)。考虑方差是非常重要的，因此有些桶可能是空的，而其他的可能有多于一个元素；我们需要保证没有桶包含过多的元素。我们再一次通过统计理论得到下面的等式：
从这个等式我们能够计算出ni2的期望值。这个计算是非常关键的，因为这是决定插入排序开销的关键因素，插入排序的最坏情况性能为O(n2)。我们计算出E[ni2]=(1-1/n)+1=(2-1/n)，可以看到E[ni2]是一个常数。这个意味着当我们将在n个桶上执行插入排序的总开销加起来之后，总的期望性能为O(n)。