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

マージソート

出典: フリー百科事典『ウィキペディア(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翻訳
英語⇒日本語日本語⇒英語
  

マージソートに関連した本

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

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

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

   

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

画像から探す

和田浦海水浴場

Windows 7

ラオスアンタエウス

CS-12M 海底同軸ケーブル中継装置

カビ

ランドクルーザー プラド

BMW Z4 ロードスター

820SH





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

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

©2015 Weblio RSS