基本情報技術者 予想問題｜A 第15問

解説

正解はア。マージソートは、配列を半分ずつに分割していき、要素1個になるまで分けた後、整列済みの列同士を併合（マージ）しながら全体を整列する分割統治法のアルゴリズムである。分割の深さがlog n段で、各段の併合に約n回の比較が必要なため、計算量はデータの並び方によらず最悪でもO(n log n)で安定している。また、同じ値の要素の元の順序が保存される安定ソートである。イの「最悪O(n^2)」はクイックソートやバブルソートに当てはまる記述で誤り。ウは誤りで、併合用の作業領域としてO(n)の追加メモリを要する点がマージソートの弱点である。エも誤りで、典型的な実装は再帰を用いる。基本情報では、各整列法の計算量・安定性・追加メモリの比較が頻出であり、「マージソート＝安定・最悪O(n log n)・追加メモリ必要」と整理して覚えておきたい。