マージソート マージソートの概要

マージソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2014/05/14 07:34 UTC 版)

マージソート
Merge-sort-example-300px.gif
マージソートの例。まずリストを小さな単位に分け、二つのリストをそれぞれの要素の先頭を比較してマージする。最後までこの操作をくり返すと、リストはソートされている。
クラス ソート
データ構造 配列
最悪計算時間 O(n \log n)
最良計算時間

O(n \log n) typical,

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

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 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

  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


「マージソート」の続きの解説一覧





マージソートと同じ種類の言葉


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

「マージソート」の関連用語

マージソートのお隣キーワード

   

英語⇒日本語
日本語⇒英語
   
検索ランキング

画像から探す




マージソートのページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのマージソート (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2014 Weblio RSS