平均ケースの時間計算量がO(n log n)となるソートアルゴリズムはどれか？

クイックソートは典型的に平均時間計算量がO(n log n)であり、最悪ケースはピボットの選び方によってO(n^2)になります。バブルソートや選択ソートは平均・最悪ともにO(n^2)であり、挿入ソートは入力がほぼ整列している場合は高速ですが平均はO(n^2)です。クイックソートは実装やピボット選択（中央値選択等）によって安定的に良い平均性能を発揮します。