マージソート
マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする[1]。
（ナイーブな）クイックソートと比べると、最悪計算量は少ない[1]。ランダムなデータでは通常、クイックソートのほうが速い。
アルゴリズム
基本的な手順は以下の通りである。
- データ列を分割する（通常、等分する）
- 各々をソートする
- 二つのソートされたデータ列をマージする
2番目のステップでは、マージソートを再帰的に適用する。
マージは、データ列の先頭同士を比べ小さい方をデータ列から取り出し、残りのデータ列に対して再帰的に適用する。
ソートすべきデータ列が部分的に順次得られる場合、オンラインアルゴリズムとして部分データ列をソートして後でマージするという変形も可能である。
また、高速化の手法として、自明な列（要素数がたかだか1個）になるまで細分割せず、ある程度になったら別の単純なアルゴリズムに切り替える、というものがある[1]。
他に特殊な応用例として、テープ（のようなシーケンシャルアクセスメディア）に収められたデータをソートする、というものがある。2本のテープの先頭部分にある、すでに整列しているとみなせる部分列をマージする、という操作により、より長い整列した列が得られる。出力先となる2本のテープを切り替えながらこの操作を繰り返せば、元の2本のテープにあった整列された部分列のそれぞれがマージされ、部分列の個数が約半分になった、新しい2本のテープが得られる。コピー元とコピー先のテープを入れ替え、同じ操作を繰り返す。最終的に、テープを切り替えることなく、1本のテープに全てのデータが出力されたら完了である。
実装例
Ruby
def mergesort lst
return _mergesort_ lst.dup # 副作用で配列が壊れるので、複製を渡す
end
def _mergesort_ lst
if (len = lst.size) <= 1 then
return lst
end
# pop メソッドの返す値と副作用の両方を利用して、lst を二分する
lst2 = lst.pop(len >> 1)
return _merge_(_mergesort_(lst), _mergesort_(lst2))
end
def _merge_ lst1, lst2
len1, len2 = lst1.size, lst2.size
result = Array.new(len1 + len2)
a, b = lst1[0], lst2[0]
i, j, k = 0, 0, 0
loop {
if a <= b then
result[i] = a
i += 1 ; j += 1
break unless j < len1
a = lst1[j]
else
result[i] = b
i += 1 ; k += 1
break unless k < len2
b = lst2[k]
end
}
while j < len1 do
result[i] = lst1[j]
i += 1 ; j += 1
end
while k < len2 do
result[i] = lst2[k]
i += 1 ; k += 1
end
return result
endHaskell
（※ Haskellのリストは「長さを測って半分ずつに分ける」という操作には適さないため、要素を1個ずつ振り分ける関数を使っている。この実装では安定ではない）
mergesort lst =
let merge xx yy = case (xx, yy) of
([], []) -> []
(xxs, []) -> xxs
([], yys) -> yys
(x : xs, y : ys) -> if x < y then x : merge xs yy else y : merge xx ys
split l = case l of
[] -> ([], [])
[_] -> (l, [])
x : y : rest -> let (xs, ys) = split rest in (x : xs, y : ys)
in case lst of
[] -> []
[_] -> lst
_ -> let (a, b) = split lst
in merge (mergesort a) (mergesort b)アルゴリズムの動作例
初期データ: 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
