マージソートとは？

詳細解説

マージソート（Merge Sort）は、配列を半分に分割する操作を再帰的に繰り返し（分割フェーズ）、最小単位（1要素）になったら整列済みとみなして隣接する2つの整列済み部分列を1つの整列済み列に統合（マージフェーズ）していくアルゴリズムです。クイックソートと同じく分割統治型ですが、マージソートは**最悪ケースでもO(n log n)**が保証されます。安定ソート（同値要素の相対順序を保つ）であるため、Javaのコレクションソートなど安定性が求められる標準ライブラリで採用されています。欠点は、マージ時に元配列と同サイズの補助配列が必要なため**空間計算量O(n)**になることです。FE試験では「マージのトレース（2つの整列済み配列を1つにまとめる手順）」「クイックソートとの比較（安定性・最悪計算量・空間計算量）」が典型問題です。外部ソート（データがメモリに収まらない場合のHDDソート）にも応用されます。

FE試験での出題ポイント

• 1最悪ケースでもO(n log n)が保証される（クイックソートと最大の差異）
• 2安定ソート（同値要素の相対順序保持）→Java標準ライブラリ採用
• 3空間計算量O(n)：マージ用の補助配列が必要
• 4マージフェーズ：2つの整列済み部分をポインタで比較・統合するトレース

関連用語