マージソートとは
マージソート（Merge Sort / 併合ソート）とは、並べ替えアルゴリズムの一つで、データ群を要素が1個になるまで細かく（半分ずつに）分解したあと、並び順が正しくなるように合体（マージ）させながら、元の大きさに戻していくことで整列を行う手法です。常に安定した時間で処理できる性質があり、データの順序が崩れない「安定ソート」であることも特徴です。
具体例
2つの「すでに数字順に綺麗に並んだトランプの束」を1つにまとめる際、それぞれの束の先頭（一番上）にあるカードをめくって小さい方を新しい束に重ねていくことで、最初から綺麗な1つの束（マージ結果）を作る仕組みです。
分解フェーズ: [4, 2, 1, 3] --> [4, 2] と [1, 3] --> [4], [2], [1], [3] (最小単位まで)
合体フェーズ: [4], [2] をマージ --> [2, 4]
[1], [3] をマージ --> [1, 3]
[2, 4] と [1, 3] をマージ --> [1, 2, 3, 4] (完成)もう少し詳しく
マージソート（Merge Sort）は、クイックソートと同様に「分割統治法」に基づく整列アルゴリズムです。具体的な手順は以下の通りです。まず、配列全体の要素数が1になるまで、中央で半分に分割する処理を再帰的に繰り返します。要素数が1の配列はそれ自体が「整列済み」とみなせます。次に、分割された隣り合う配列同士を、大小関係を比較しながら順序正しく「マージ（併合）」して1つの配列に戻します。このマージ処理を元の配列サイズに戻るまで繰り返すことで、最終的に全体が整列されます。マージソートの最大のメリットは、入力データの初期配置（整列度合い）に関わらず、最悪・最良・平均のすべての場合において時間計算量が常に O(N log N) で安定している点です。また、同値の要素の順序が維持される「安定ソート」でもあります。一方のデメリットは、マージ処理を行う際に、データを一時的に退避させるための「元の配列と同じサイズ（O(N)）の追加の作業用メモリ領域」が必要となるため、メモリ効率の面でクイックソートやヒープソートに劣る点にあります。
試験でのポイント
試験では、マージソートの時間計算量が最悪・平均・最良を問わず常に O(N log N) であることや、マージを行う際に追加のメモリ領域（領域計算量 O(N)）が必要であるという特徴が頻出です。また、具体的なマージ（併合）の処理において、「2つのソート済み配列の先頭要素同士を比較し、小さい方を新しい配列に移動する」というポインタ制御アルゴリズムをトレースする問題や、安定ソートであるという利点が問われます。
関連する用語
マージ（2つのソート済みデータを1つに統合する処理）、安定ソート（ソート後に同値の順番が入れ替わらない整列方式）、領域計算量（アルゴリズム実行時に必要となる追加メモリ量を表す指標）。