先日、McIlroy の論文A Killer Adversary for QuicksortArrays.sortで説明されている手法を使用して、 O(n 2 ) 動作をトリガーするプリミティブ型の入力を生成するプレゼンテーションを見ました。このシーケンスにより、pivot の選択により常に配列サイズが定数分だけ減少し、JavaArrays.sort関数がスタック オーバーフローを引き起こしました。
JDK のソース ファイルによると、Arrays.sort1クイックソート実装関数には、スタック オーバーフローを防ぐためのガードがありません。並べ替えルーチンが 2 つの再帰呼び出しを起動せず、代わりに while ループを使用して現在のスタック フレームを大きな部分配列に再利用し、(小さな部分配列で) 1 回だけ再帰することで、クイック ソートがスタック オーバーフローしないようにすることは常に可能です。これにより、パフォーマンスの低下が最小限に抑えられ、サイズ n の入力でスタックの深さが O(log n) スタック フレームを超えることはないため、適切なサイズの入力に対してスタック オーバーフローが発生することが不可能になります。著者は、イントロソートを使用することもできましたこれは、クイックソートの再帰の深さが制限を超えた場合に、最悪のケースの O(n log n) ソート アルゴリズムに切り替えるようにクイックソートを変更して、これを防ぎます。
Arrays.sortの作成者がこれを選択しなかった理由はありますか? 組み込みの並べ替えアルゴリズムがスタック オーバーフローを引き起こす可能性があることは深刻な問題のように思えます。繰り返しスタック オーバーフローをトリガーすることで、そのようなシステムに対して DoS 攻撃を開始できるからです。