マージソート

出典: フリー百科事典『ウィキペディア（Wikipedia）』

マージソートは、分割統治法を用いたソートのアルゴリズムの一つ。整列してある2者の配列を併合し1つにするもの。並列処理にも適している。

n個のデータを含む配列をソートする場合、最悪計算量O(n log n)で、安定ソートだが、O(n)の外部記憶を必要とする。^[1]

クイックソートと比べると、最悪計算量は少ない。しかし、ランダムな数列で実験すると、実際上はクイックソートの方が速いことが多い。

目次 1 アルゴリズム 2 アルゴリズムの動作例 3 脚注 4 関連項目 5 外部リンク

[編集] アルゴリズム

1. データ列を二分割する （通常、二等分する）
2. 各々をソートする
3. 二つのソートされたデータ列をマージする

2番目のステップでは、マージソートを再帰的に適用する。

マージは、データ列の先頭同士を比べ小さい方をデータ列から取り出し、残りのデータ列に対して再帰的に適用する。

ソートすべきデータ列が部分的に順次得られる場合、オンラインアルゴリズムとして部分データ列をソートして後でマージするという変形も可能である。

[編集] アルゴリズムの動作例

初期データ: 8 4 3 7 6 5 2 1

1. データ列を二分割する。

   8 4 3 7 | 6 5 2 1

2. もう一度、二分割する。

   8 4 | 3 7 | 6 5 | 2 1

3. 各データ列にデータ数が2以下になったところで、各データ列内のデータをソートする。

   4 8 | 3 7 | 5 6 | 1 2

4. この例の場合は、右2つのデータ列、左2つのデータ列をそれぞれマージとソートし、2つのデータ列にする。

   3 4 7 8 | 1 2 5 6

5. 2つのデータ列をマージとソートする。

   1 2 3 4 5 6 7 8

[編集] 脚注

1. ^ 計算時間をO(n (log n)²)に落とせば、内部ソートに変更できるという研究結果もある。

[編集] 関連項目

• マージ

[編集] 外部リンク

• マージソートコード