マージソート
読み：マージソート
外語：merge sort
ソートアルゴリズムの一つ。
すでにソート済みの2つの数列を掛け合わせて新しい1つのソート済み数列を作るという動作を繰り返すことにより実現するソート。
A={2,5,9,11} B={3,5,6,10}という2つのソート済みの数列があるとする。このとき、一番最初の数値(Aは2、Bは3)を比較し、小さいほうである2を取り出し、新しい数列Cに入れる。以下Bの3、Aの5、Bの5、Bの6、Aの9、Bの10、Aの11と取り出していき、数列CはC={2,3,5,5,6,9,10,11}となる。この操作をマージといい、この動作を繰り返すことによってソートができるのである。
最悪計算量がO(n log n)のソートの中では唯一の安定ソートである。しかし、作業領域が必要なため巨大なデータをソートするには適していない。
マージソートの途中経過
5 | 8 | 6 | 1 | 7 | 11 | 5 | 3 初期状態
5 8 | 1 6 | 7 11 | 3 5 1回目のマージ操作
1 5 6 8 | 3 5 7 11 2回目のマージ操作
1 3 5 5 6 7 8 11 3回目のマージ操作
再検索