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

マージソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/06/21 10:29 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]

他に特殊な応用例として、外部ソートの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


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





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


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

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

辞書ショートカット

カテゴリ一覧

全て

ビジネス

業界用語

コンピュータ

電車

自動車・バイク

工学

建築・不動産

学問

文化

生活

ヘルスケア

趣味

スポーツ

生物

食品

人名

方言

辞書・百科事典

すべての辞書の索引

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

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

   

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

画像から探す

嘉瀬川

ヨーロッパミヤマクワガタ

フォームドアスファルト舗装

いも鎚

自転車以外の軽車両通行止め

ウエス

畑

白山神社境内菩提林の杉と蘚苔





マージソートのページの著作権
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