マージソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
マージソート
Merge-sort-example-300px.gif
マージソートの例。まずリストを小さな単位に分け、二つのリストをそれぞれの要素の先頭を比較してマージする。最後までこの操作をくり返すと、リストはソートされている。
クラス ソート
データ構造 配列
最悪計算時間 O(n \log n)
最良計算時間

O(n \log n) typical,

O(n) natural variant
平均計算時間 O(n \log n)
最悪空間計算量 O(n) 外部記憶
マージソートの様子

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

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

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

アルゴリズム[編集]

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

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

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

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

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

また、高速化の手法として、自明な列(要素数がたかだか1個)になるまで細分割せず、ある程度になったら別の単純なアルゴリズムに切り替える、というものがある[1]

他に特殊な応用例として、外部ソートの1手法でテープ(のようなシーケンシャルアクセスメディア)に収められたデータをソートする、というものがある。最も単純な、4本のテープを2本ずつ使う「平衡2系列マージ」を例に説明する。まず元のデータから、利用可能な内部記憶をできるだけ使って、部分的に整列されている列をテープに書き出す。この時、2本のテープに交互に書き出すようにする。

次に、2本のテープのそれぞれの先頭部分にある、それぞれの部分列をマージしながら、別の2本のテープに交互に書き出す。この操作により、より長い整列した列が得られる。全てのマージが終わったら、コピー元とコピー先を入れ替え、同様に繰り返す。繰返し毎に各部分列の長さは約2倍に、列の個数は約半分になると期待できる。

最終的に、テープを切り替えることなく、1本のテープに全てのデータが出力されたら完了である。この技法はコンピュータがまだ高価で、テープが大容量外部記憶の主力だった時代にさかんに研究され、さまざまなバリエーションが編み出された。『The Art of Computer Programming』の§5.4にそれらの詳細がある。

実装例[編集]

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 :: Ord t => [t] -> [t]
mergesort lst = case lst of
   []  -> lst
   [_] -> lst
   _   -> merge (mergesort a) (mergesort b)
      where
         (a, b)  =  split lst

         merge []  []   =  []
         merge xxs []   =  xxs
         merge []  yys  =  yys
         merge xxs@(x : xs) yys@(y : ys)
            | x < y      =  x : (merge xs yys)
            | otherwise  =  y : (merge xxs ys)

         split []         =  ([], [])
         split ~(x : xs)  =  (x : zs, ys)
            where
               (ys, zs) = split 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

関連項目[編集]

外部リンク[編集]