n個の要素を整列するとき、要素の初期配置に関わらず最悪の場合でも時間計算量がO(n log n)となることが保証されている整列アルゴリズムはどれか。

なぜ ア は間違いか

クイックソートは平均O(n log n)で非常に高速ですが、ピボット（基準値）の選び方が悪いと分割が極端に偏ります。例えば既にソート済みの列に対して常に最小値をピボットに選ぶと、毎回1要素しか分割されず最悪O(n²)に陥ります。ランダムピボット選択で実用上は回避できますが、理論的な最悪保証はありません。

なぜ イ は間違いか

バブルソートは隣接する要素を比較・交換し続ける最もシンプルな方法です。偶然ほぼ整列済みなら最良O(n)になりますが、逆順に並んだ列では最悪O(n²)の比較が必要になります。直感的で実装は簡単ですが、大規模データには向きません。

なぜ エ は間違いか

挿入ソートは手持ちのトランプを1枚ずつ適切な位置に差し込む感覚で動く直感的なアルゴリズムです。ほぼ整列済みの列や少量データではO(n)に近い高速動作を見せますが、逆順の列では各要素を毎回先頭まで移動させる必要があり最悪O(n²)になります。