[解決済み] なぜクイックソートはマージソートより優れているのですか？

質問

面接でこんな質問をされました。どちらもO(nlogn)ですが、ほとんどの人はMergesortではなくQuicksortを使っています。なぜでしょうか？

どのように解決するのですか？

クイックソートはO( n ² ) の最悪ランタイムと O( n ログ n )の平均実行時間です。しかし、多くのシナリオでマージソートより優れています。なぜなら、アルゴリズムの実行時間には多くの要因が影響し、それらをすべて考慮すると、クイックソートは勝っているからです。

特に、よく言われるソートアルゴリズムの実行時間とは、データをソートするために必要な比較回数やスワップ回数のことである。これは、特に基盤となるハードウェア設計に依存しないため、確かに性能の良い指標となる。しかし、現在のハードウェアでは、参照の局所性（つまり、キャッシュにあるであろう要素をたくさん読み込むかどうか）など、他のものも重要な役割を担っている。特にクイックソートは追加スペースをほとんど必要とせず、良好なキャッシュの局所性を示すので、多くの場合マージソートよりも高速になります。

さらに、クイックソートの最悪実行時間であるO( n ² )は、ピボットの適切な選択（ランダムに選ぶなど）により、ほぼ完全に解決されます（これは優れた戦略です）。

実際には、最近のクイックソートの実装の多く (特に libstdc++ の std::sort ) は、実際には イントロソート であり、その理論的な最悪のケースは O( n ログ n )、マージソートと同じです。これは、再帰の深さを制限し、別のアルゴリズムに切り替えることで実現されます ( ヒープソート を超えると n .