整列（ソート）アルゴリズムの計算量に関する次の記述のうち、適切なものはどれか。ただし、n はデータ数とする。
正解・解説を確認する
解答正解 5
マージソートは、分割の段数が log₂n で、各段の併合の作業量が n に比例するため、最悪でも O(n log n) である（ただし作業用の領域が別途必要）。クイックソートは平均では最速級でも最悪は O(n²) で、バブル・選択・挿入ソートは基本的に O(n²) である。計算量の記述では、平均・最悪・最良のどれを指すかを区別して読むことが大切である。
選択肢ごとの判定
1クイックソートの平均は O(n log n) だが、分割が極端に偏る最悪の場合は O(n²) となる。
2バブルソートは隣接要素の比較・交換を繰り返すため、平均・最悪とも O(n²) である。
3挿入ソートが O(n) になるのは、すでにほぼ整列済みの場合。最悪（逆順）は O(n²) である。
4選択ソートは整列済みでも最小値を探す比較を毎回行うため、常に O(n²) の比較が必要である。
5正しい。列を半分に分けて整列し併合する操作を log n 段繰り返し、各段で n 回程度の処理を行うため、入力によらず O(n log n) である。