マージソート

マージソート

クラス	ソート
データ構造	配列
最悪計算時間	O(n log n)

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

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

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

アルゴリズム

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

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

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

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

また、高速化の手法として、配列がある程度細かい区間に分かれたら、それぞれを挿入ソートのような単純なアルゴリズムに切り替えるということも行われる。

Rubyでの実装例

def merge(left, right)
        final = []
        until left.empty? or right.empty?
                final << ( left.first < right.first ? left.shift : right.shift )
        end
        final + left + right
end

アルゴリズムの動作例

初期データ: 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

関連項目

• マージ

外部リンク

• マージソートコード(英語)