テクノロジ系出題頻度 3/3
マージソート
まーじそーと
定義
データを半分に分割して再帰的にソートし併合する分割統治ソート。常にO(n log n)。
詳細解説
1945年フォン・ノイマン考案。配列を半分に分け、それぞれを再帰的にソートしてから昇順に併合（マージ）する。常にO(n log n)で安定ソート。クイックソートと異なり最悪ケースでも安定して高速だが、O(n)の追加メモリが必要。連結リストでは追加メモリを必要とせず効率的。外部ソート（メモリに乗り切らない大規模データ）でも基本となるアルゴリズム。Timsortはマージソートと挿入ソートの組合せで、Python・Java等の標準実装に採用。
「マージソート」が出る問題
関連用語
よくある質問
Q. マージソートとは何ですか？
A. データを半分に分割して再帰的にソートし併合する分割統治ソート。常にO(n log n)。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。