マージソート | 応用情報技術者試験
マージソートとは
マージソート（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] (完成)
もう少し詳しく