为什么快速排序的JDK实现有堆栈溢出的风险？

Question

前几天我看了一个演讲，演讲者使用了McIlroy的论文《快速排序的致命对手》中概述的技术来生成数组的输入。为将触发O（n^{2行为的基元类型排序。该序列导致pivot选择总是将数组大小减少一个常数，这导致了Java数组。sort函数导致堆栈溢出。}

根据JDK的源文件，Arrays.sort1快速排序实现函数没有防止堆栈溢出的保护措施。通过让排序例程不触发两次递归调用，而是使用时循环为较大的子数组重用当前堆栈帧，并且只递归一次（在较小的子数组上），始终可以使快速排序永远不会堆栈溢出。这会导致最小的性能下降，并且使得任何合理大小的输入都不可能导致堆栈溢出，因为在大小为n的输入上堆栈深度永远不会超过O（log n）堆栈帧。为了防止这种情况发生，作者还可以使用内隐排序算法，当快速排序递归深度超过某个限制时，它修改快速排序以切换到最坏情况下的O（n log n）排序算法。

有什么理由让数组的作者。排序没有选择这样做？内置排序算法可能导致堆栈溢出，这似乎是一个严重的问题，因为它可能通过触发重复的堆栈溢出来对此类系统发起DoS攻击。

Answer 1

为什么？因为解决这个问题太过分了。

所使用的算法在除了异常情况之外的所有情况下都是稳定的，如果这些情况比通常情况下更有可能发生，那么这种情况将在外部得到防范。这就是为什么他们有API留档来定义幕后使用的算法。所以你可以防御它。

破坏所提出算法的特定顺序的可能性非常小。

我希望如果您仔细观察，就会发现一些数据集会导致几乎所有标准JVM结构崩溃。保护它们的成本是多少？这一成本值得付出努力吗？由于防御措施，算法不可避免地会退化。