次のソートアルゴリズムのうち、入力データの並び方にかかわらず、最悪時間計算量が O(n log n) で抑えられるものはどれですか？

ヒープソートは、配列から最大ヒープを構築する処理が O(n)、その後、最大値を取り出して再構築する操作を n 回繰り返し、各操作が O(log n) なので、どんな入力でも最悪 O(n log n) で終わります。クイックソートは平均で O(n log n) ですが、ピボットの選び方が悪く、すでに整列済みの配列などが入力されると最悪 O(n^2) になります。バブルソートと挿入ソートも最悪 O(n^2) です。