マージソートとは？

マージソートの意味

データを半分ずつに分けていき、要素1個まで細かくしてから、整列済みの列どうしを併合（マージ）して1つにまとめる整列方法。最悪でもO(n log n)を保証する。ただし併合用に元データと同程度の作業領域が必要で、外部ソートの基礎にもなる点がFEで問われる。

マージソートの具体例

[3,1,4,2]を[3,1]と[4,2]に分け、それぞれ[1,3]と[2,4]に整列。次に両者の先頭を比べながら小さい順に取り出し、1→2→3→4の順に並べて[1,2,3,4]を得る。併合は両列を1回ずつ走査するのでその段はO(n)。

マージソートは試験でどう引っ掛けられる？

「追加の記憶領域がほとんど不要」はクイックソートの説明であり、マージソートはO(n)の作業領域を要する。一方で最悪計算量の保証はマージソート側にある。同値の順序が保たれる安定なソートである点も対比で問われる。

マージソートと関連する用語

• クイックソート・マージソート・ヒープソート
• 内部ソートと外部ソート
• 安定ソート

マージソートが出た過去問

• アルゴリズム設計としての分割統治法に関する記述として、適切なものはどれか。

  正解：全体を幾つかの小さな問題に分割して、それぞれの小さな問題を独立に処理した結果をつなぎ合わせて、最終的に元の問題を解決する方法である。

  要点：分割統治法は小問題に分けて解き結果を統合する

  分割統治法は、解きにくい大きな問題を同じ構造の小さな部分問題に分割し、それぞれを独立に解いてから結果を統合して元の問題の解を得る手法である。マージソートやクイックソート、二分探索などが代表例で、再帰的に分割していく点が特徴である。

  出典：令和3年度 春期 高度共通_午前I試験 am1 問3（IPA）