応用情報技術者 予想問題｜練習問題 第6問

解説

マージソートは列を半分ずつに分割し、整列済みの部分列を併合（マージ）していく分割統治法のアルゴリズムである。分割の深さがlog n段、各段での併合に合計O(n)を要するため、計算量は最悪・平均ともO(n log n)となる。線形探索は先頭から順に調べるだけなのでO(n)、バブルソートは隣接要素の交換を繰り返す二重ループでO(n²)、標準的な行列積は3重ループでO(n³)であり、いずれも該当しない。マージソートは入力によらずO(n log n)で安定して動作する点が強みで、平均はO(n log n)だが最悪O(n²)となるクイックソートと対比して覚えるとよい。比較に基づく整列の理論的下限がO(n log n)である点も押さえたい。