技術士 第一次試験 基礎科目 2群 情報・論理 練習問題 第4問: 整列（ソート）のアルゴリズムの時間計算量に関する記述として、最も適切なものはどれか。ただし、n は整列するデータの件数とする。

「マージソートは、最悪の場合でも O(n log n) の時間で整列を終える」が適切です。NIST Dictionary of Algorithms and Data Structures（DADS）は、マージソートをデータを 2 つに分けてそれぞれを再帰的に整列し、併合する方法とし、実行時間を Θ(n log n) としています。

Θ は上下からの評価なので、最悪の場合も O(n log n) です。クイックソートは、DADS で最悪の場合 Θ(n²)、通常は O(n log n) とされ、ピボットの選び方によっては n² に比例する時間がかかります。

挿入ソートは要素の移動のため O(n²) とされ、常に O(n) ではありません。バブルソートは任意のデータで O(n²) で、最悪の場合に O(n log n) にはなりません。

選択ソートは残りから最小のものを探して置くことを繰り返すため、実行時間は Θ(n²) で、整列済みでも O(n) にはなりません。出題範囲は IPA 基本情報技術者試験シラバス Ver.9.2 の「整列・併合・探索のアルゴリズム」と「計算量」に当たります。