マージソートとは？まーじそーと
マージソートとは、データを半分ずつに分けていき、要素1個まで細かくしてから、整列済みの列どうしを併合（マージ）して1つにまとめる整列方法。最悪でもO(n log n)を保証する。ただし併合用に元データと同程度の作業領域が必要で、外部ソートの基礎にもなる点がFEで問われる。
最終更新：2026-10-07
この語が出る過去問を解く →具体例
[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)の作業領域を要する。一方で最悪計算量の保証はマージソート側にある。同値の順序が保たれる安定なソートである点も対比で問われる。
関連用語
出た過去問
出典・参考
公式シラバスの1 基礎理論 ＞ 2. アルゴリズム ＞ (2) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。