マージソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
マージソート
マージソートの様子
クラス ソート
データ構造 配列
最悪計算時間 O(n log n)

マージソートは、ソートアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。

n個のデータを含む配列をソートする場合、最悪計算量O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなソートも提案されているが、通常O(n)の外部記憶を必要とする[1]

(ナイーブな)クイックソートと比べると、最悪計算量は少ない[1]ランダムなデータでは通常、クイックソートのほうが速い。

目次

アルゴリズム [編集]

基本的な手順は以下の通りである。

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

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

  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. ^ a b c 奥村晴彦 『C言語による最新アルゴリズム事典』 技術評論社1991年、267頁。ISBN 4-87408-414-1

関連項目 [編集]

外部リンク [編集]