トップページ > コンテンツ > 数学・アルゴリズム関連メモ > 数学・情報工学的 > ソートの種類 > マージソート

整列された2つの配列を1つに併合することでソートする手法。
最悪でもNlogNの計算量で済むが、マージソートの欠点は配列の長さに比例する作業領域が
必要となることである。

平均計算量	O(NlogN)
最悪計算量	O(NlogN)

3

8

4

7

2

1

6

5

というデータがあったする。まず2分する。

3	8	4	7
2	1	6	5

データが2つになるまでさらに二分すると、
(3,8),(4,7),(2,1),(6,5)の比較となる。
それぞれ並べ替え後、
[(3,8),(4,7)]と[(1,2),(5,6)]でそれぞれ併合する。
すると、(3,4,7,8)と(1,2,5,6)となるので
さらに結合し、

1

2

3

4

5

6

7

8

を得る。