面接中にこの質問を受けました。どちらも O(nlogn) ですが、ほとんどの人はマージソートではなくクイックソートを使用しています。なぜでしょうか?
ベストアンサー1
クイックソートは、最悪の場合の実行時間が O( n 2 )、平均的な場合の実行時間が O( n log n ) です。ただし、アルゴリズムの実行時間には多くの要因が影響するため、多くのシナリオではマージソートよりも優れており、それらすべてを総合するとクイックソートが勝ります。
特に、よく引用されるソート アルゴリズムの実行時間は、データをソートするために必要な比較の数またはスワップの数を指します。これは確かにパフォーマンスの優れた指標であり、特に基盤となるハードウェア設計に依存しないためです。ただし、参照の局所性 (つまり、キャッシュ内にある可能性のある要素を多数読み取るかどうか) などの他の要素も、現在のハードウェアでは重要な役割を果たします。特にクイックソートは、追加のスペースをほとんど必要とせず、優れたキャッシュ局所性を示すため、多くの場合、マージ ソートよりも高速になります。
さらに、ピボットをランダムに選択するなど、適切な選択を行うことで、クイックソートの最悪実行時間である O( n 2 ) をほぼ完全に回避することは非常に簡単です (これは優れた戦略です)。
実際には、クイックソートの最近の実装（特にlibstdc++のものstd::sort）の多くは、実際にはイントロソート、その理論的な最悪ケースはO( n log n )で、マージソートと同じです。これは再帰の深さを制限し、別のアルゴリズムに切り替えることで実現されます（ヒープソート) は、log nを超えると発生します。