マージソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
マージソートは、分割統治法を用いたソートのアルゴリズムの一つ。並列処理にも適している。
n個のデータを含む配列をソートする場合、最悪計算量O(n log n)で、安定ソートだが、O(n)の外部記憶を必要とする。[1]
クイックソートと比べると、最悪計算量は少ない。しかし、ランダムな数列で実験すると、実際上はクイックソートの方が速いことが多い。
目次 |
[編集] アルゴリズム
- データ列を二分割する （通常、二等分する）
- 各々をソートする
- 二つのソートされたデータ列をマージする
2番目のステップでは、マージソートを再帰的に適用する。
マージは、データ列の先頭同士を比べ小さい方をデータ列から取り出し、残りのデータ列に対して再帰的に適用する。
[編集] アルゴリズムの動作例
初期データ: 8 4 3 7 6 5 2 1
- データ列を二分割する。
- 8 4 3 7 | 6 5 2 1
- もう一度、二分割する。
- 8 4 | 3 7 | 6 5 | 2 1
- 各データ列にデータ数が2以下になったところで、各データ列内のデータをソートする。
- 4 8 | 3 7 | 5 6 | 1 2
- この例の場合は、右2つのデータ列、左2つのデータ列をそれぞれマージとソートし、2つのデータ列にする。
- 3 4 7 8 | 1 2 5 6
- 2つのデータ列をマージとソートする。
- 1 2 3 4 5 6 7 8
[編集] 脚注
- ^ 計算時間をO(n log2 n)に落とせば、内部ソートに変更できるという研究結果もある。
