ほぼ整列済みのデータに対して特に高速に動作し、完全に整列済みのデータであれば比較回数が n−1 回で済む整列アルゴリズムはどれか。

解説

正解は「挿入ソート」です。挿入ソートは、整列済みの部分列に、次の要素を後ろから比較しながら適切な位置に挿入していく方法です。データが整列済みなら、各要素は1回の比較で位置が決まるので、比較回数は n−1 回、計算量は $O(n)$ となります。最悪（逆順）の場合は $O(n^2)$ です。「選択ソート」は、未整列部分から最小値を探すために毎回残りすべての要素を比較するので、並びによらず比較回数は $n(n-1)/2$ 回です。「ヒープソート」は入力によらず $O(n\log n)$ で、整列済みでも速くなりません。「マージソート」も分割と併合を常に行うため、整列済みのデータでも $O(n\log n)$ かかります。