大規模データを高速にソートする O(n log n) アルゴリズムの代表が、クイックソートとマージソート。考え方の違いを理解しましょう。
日野 こむぎ
もっと速いソートってないの?
藤森 さやか 先生
あるわよ。
代表はクイックソートとマージソート。
両方とも平均 O(n log n) で動くわ。
青木 澪
クイックソートは「基準値 (ピボット) より小さいグループ」と「大きいグループ」に分割して、各々を再帰的にソート。
マージソートは「半分に分ける」→「個別にソート」→「合体」という分割統治法ね。
桃井 すみれ
どっちが速いんですかぁ?
藤森 さやか 先生
平均的にはクイックソートが少し速いけど、最悪ケースで O(n²) になることがあるの。
マージソートは安定ソートで、常に O(n log n) を保証するのが利点。
青木 澪
メモリ使用量はクイックソートが少なく (in-place)、マージソートは追加メモリが必要 (O(n))。
状況で使い分けるの。
日野 こむぎ
なるほどね、トレードオフかぁ。
あたしも場面で使い分けてみるね!
藤森 さやか 先生
実用的には、Pythonのsortedはハイブリッドな TimSort、C++のstd::sortは IntroSort と、複数アルゴリズムを組み合わせて最適化されているのよ。
桃井 すみれ
賢いですねぇ♪
確認クイズ
マージソートの計算量として正しいものはどれか。
- 最良も最悪も O(n log n)
- 最良 O(n)、最悪 O(n²)
- 最良 O(n)、最悪 O(n log n)
- 全て O(n²)
こたえを見る
正解: 1. 最良も最悪も O(n log n)
マージソートは入力に関係なく 常に O(n log n) で動作します。これが安定性とともにマージソートの大きな利点です。