中值排序保证递归子问题的规模都大致一样。这就意味着中值排序的平均性能是O(n log n)。但是，在最坏情况下，partition函数执行时间为O(n2)，这样就使得中值排序的性能退化到O(n2)。因此，当n个元素几乎有序的时候，即使待递归排序的子问题是非常理想化的，总体性能也会受到影响。我们在中值排序中使用一个随机化的select Pivot Index函数，来对最坏情况的数据进行测试，在这些数据上，selectPivotIndex总是返回最左边的位置。我们进行了10次试验，最好和最坏的结果都被排除，剩余8次实验的平均结果见表4-2。注意观察在最坏情况下，随着问题规模的加倍，中值排序的时间增加了4倍多，这就是经典的二次方算法的标志。
因此，看起来，任何依赖于切分的排序算法的最坏情况都会退化到O(n2)。事实上，因为这个原因，我们在图4-8已经指定了最坏情况。
幸运的是，有一个线性时间的选择算法，能够确保最坏情况仍然是O(n log n)。这个选择算法被称为BFPRT（Blum-Floyd-Pratt-Rivest-Tarjan）算法（Blum等，1973），其性能见表4-2的最后一列。在统一生成的随机化数据上执行10次试验，最好和最坏的结果都被舍弃。表4-3给出了使用不同的切分子数组方法的中值排序的性能。平均情况下，使用随机中枢选择算法的计算趋势线（见表4-3）是：
1.82*10-7*n*log(n)
而BFPRT的趋势线是：
2.35*10-6*n*log(n)
因为复杂的BFPRT算法的常数更高，所以10次运行都比较缓慢，即便如此其平均情况下的执行时间为O(n log n)。
BFPRT选择算法能够保证性能稳定，因为这个算法在一个无序数组中选择的是一个可接受的近似中值。简单来说，BFPRT将含有n个元素的数组聚集成n/4个集合，每个集合有4个元素（忽略不能组成一个大小为4的集合的元素[1]）。BFPRT然后寻找到每一个4元集合的中值，这一步的开销是多少？从早前的图4-5的二叉决策树中，你能够回忆起来只需要5次比较就能给排序4个元素，所以这一步的开销最多是(n/4)*5=1.25*n，仍然是O(n)。得到这些4元集合，每一个中值是其第三个元素。我们将这些集合的中值作为集合M，M的中值（me）和原始集合A的中值非常近似。BFPRT算法用到的一个小技巧是递归地在集合M上使用BFPRT算法。编码这个算法是非常有意思的（例4-6是我们的实现，在这里我们通过递归地寻找固定距离、间隔的元素，最少化了元素交换操作）。注意到A中元素的3*n/8个是显而易见的小于或者等于me，2*n/8个也是显而易见的大于或者等于me。因此我们能够保证切分的递归调用在左子数组不会坏于37.5%，在右子数组不会坏于75%。这样就保证了BFPRT的总体最坏性能是O(n)。
例4-6：BFPRT算法的C实现
[1]文中描述的BFPRT算法将集合分成大小为5的组，但是在基准测试中，我们的实现在分组大小为4的时候更快。