配列に対するヒープソートの特徴として、適切なものはどれか。

解説

正解は「最悪でも $O(n\log n)$ で、追加の作業領域をほとんど使わない」です。ヒープソートは、配列をその場で最大ヒープに組み替え、根の最大値を末尾と交換してヒープを縮めることを繰り返します。各取り出しが $O(\log n)$ で、それを n 回行うため、入力によらず $O(n\log n)$ です。配列の中だけで交換するので、作業領域は定数で済みます。「等しいキーをもつ要素の順序が必ず保たれる」は安定なソートの性質で、ヒープソートは離れた位置の要素を交換するため安定ではありません。「整列済みのデータに対しては $O(n)$ で終わる」のは挿入ソートの特徴です。「ピボットの選び方によって最悪 $O(n^2)$ になる」のはクイックソートの特徴です。