マージソートと外部整列とは？
マージソートと外部整列とは、列を半分に分けてそれぞれ整列し、整列済みの2列を先頭から比較しながら併合する整列法。データの並びによらず常にO(n log n)を保証し、主記憶に収まらない大量データを分割して整列・併合する外部整列の基礎にもなっている。
まーじそーととがいぶせいれつ
マージソートと外部整列の意味
列を半分に分けてそれぞれ整列し、整列済みの2列を先頭から比較しながら併合する整列法。データの並びによらず常にO(n log n)を保証し、主記憶に収まらない大量データを分割して整列・併合する外部整列の基礎にもなっている。
マージソートと外部整列の具体例
1億件のログを整列する際、主記憶に収まる単位で読み込んで整列し中間ファイルに書き出す。次に複数の中間ファイルの先頭を比べながら1本に併合していく。この方式は逐次読み書きが中心なので、ディスクとの相性がよい。
マージソートと外部整列は試験でどう引っ掛けられる？
クイックソートと違い作業用の領域をn個分必要とする（配列の場合）。一方で最悪でもO(n log n)を保証し、比較が等しいときに元の順序を保つ安定ソートである点が、クイックソートとの使い分けの根拠になる。
マージソートと外部整列と関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。