结论

中值排序做了很多不需要做的事。虽然生成的子问题是最优的（因为它们都是原始问题规模的一半左右），但产生子问题的额外开销应该考虑。在“快速排序”一节中，我们将会看到，随机地选择pivotIndex就足够了，这样就能够避免退化的情况（如果原始数组是有序的，这种情况很可能会发生）。