マージソート

ソートアルゴリズムの一つ。

すでにソート済みの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回目のマージ操作

通信用語の基礎知識検索システム WDIC Explorer Version 7.04a (27-May-2022)