マージソート
 |
|
| クラス | ソート |
|---|---|
| データ構造 | 配列 |
| 最悪計算時間 | O(n log n) |
マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を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 end
Haskell [編集]
（※ 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 lst = case lst of > [] -> ([], []) > [_] -> (lst, []) > x : y : rest -> let (xs, ys) = split rest in (x : xs, y : ys) > in case lst of > [] -> lst > [_] -> lst > _ -> let (a, b) = split lst > in merge (mergesort a) (mergesort b)
上記のHaskellによるマージソートは、マージソートの重要な特徴の一つである安定性を備えていない。Haskellによる安定なマージソートの実装は以下のようになる。
import System.Random (getStdGen, randomRs) import Data.Ord (comparing) import Data.List (sortBy) -- sortBy はシステム標準の安定なソート -- マージソート mergesort :: (Ord a) => [a] -> [a] mergesort = mergesortBy compare -- 比較器付きマージソート mergesortBy :: (a -> a -> Ordering) -> [a] -> [a] mergesortBy _ [] = [] -- 空系列をソートすれば空系列である mergesortBy cmp xxs = mergesortN (length xxs) xxs -- cmp : 比較器 -- xxs : ソートする系列 where -- ソート済みの系列同士をマージ(併合)する merge xs [] = xs merge [] xs = xs merge lhs@(x:xs) rhs@(y:ys) -- lhs と rhs をマージする | cmp y x == LT = y:merge lhs ys -- 要注意(安定性の要) | otherwise = x:merge xs rhs -- マージソート本体 mergesortN 1 xs = xs mergesortN 2 [x, y] = if cmp y x == LT then [y, x] else [x, y] -- 高速化のためのコード mergesortN n xs = merge sorted_lhs sorted_rhs -- n : ソートする系列の長さ -- xs : ソートする系列 where m = n `div` 2 (lhs, rhs) = splitAt m xs -- 系列を左右に分割する sorted_lhs = mergesortN m lhs -- 左の系列を再帰的にソート sorted_rhs = mergesortN (n - m) rhs -- 右の系列を再帰的にソート -- 複数のフィールドのあるデータ用の比較器。a がキーの型 cmpfst :: (Ord a) => (a, b) -> (a, b) -> Ordering cmpfst = comparing fst -- 安定性の判定。OK が安定、NG が不安定 check :: Bool -> String check True = "OK: stable" check False = "NG: unstable" -- このマージソートの安定性をチェックする main = do g <- getStdGen let xs = zip (take 100000 $ randomRs (0,99) g :: [Int]) [0..] -- 乱数列生成 putStrLn $ check $ mergesortBy cmpfst xs == sortBy cmpfst xs
アルゴリズムの動作例 [編集]
初期データ: 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
脚注 [編集]
関連項目 [編集]
外部リンク [編集]
|
||||||||||||||||||||||||||||||||
