配列を整列するマージソートの、クイックソートと比べたときの長所として、適切なものはどれか。

解説

正解は「最悪の場合でも時間計算量が $O(n\log n)$ である」です。マージソートは、常にデータを半分ずつに分割して整列済みの列を併合するため、入力の並びによらず $O(n\log n)$ で整列できます。等しい値の順序が保たれる安定なソートにできる点も長所です。一方、クイックソートはピボットの選び方が悪いと最悪 $O(n^2)$ になります。「追加の作業領域をほとんど必要としない」のはクイックソートやヒープソートの特徴で、配列のマージソートは併合のために $O(n)$ の作業領域を使います。「平均的な実行時間が常にクイックソートより短い」は誤りで、実際にはクイックソートの方が速いことが多くあります。「整列済みのデータに対して $O(n)$ で終了する」のは挿入ソートの特徴です。