マージソートとは？まーじそーと
マージソートとは、データを半分ずつに分けていき、要素1個まで細かくしてから、整列済みの列どうしを併合（マージ）して1つにまとめる整列方法。最悪の場合でも、処理時間の伸び方はO(n log n)（データ数nが2倍になると時間は2倍より少し多い程度に増える）で済むことが保証される。ただし併合用に元データと同程度の作業領域が必要で、主記憶に入りきらない大量のデータを補助記憶を使って整列する外部ソートの基礎にもなる点が、基本情報技術者試験で問われる。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →具体例
[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) 代表的なアルゴリズムに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。