平均計算量が O(n log n) とされるアルゴリズムはどれか

クイックソートは平均計算量が O(n log n) であり、分割統治法に基づきピボットで配列を分割して再帰的にソートします。しかし最悪ケースでは O(n^2) になり得るため、ランダム化やピボット選択方式で実用上の性能を安定させます。ヒープソートやマージソートも O(n log n) で、安定性や追加メモリの有無で使い分けられます。