マージソート

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。n個のデータを含む配列をソートする場合、最悪計算量Oである。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースなバリエーションも提案されているが、一般には、Oの追加の作業記憶領域を必要とする。

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

1945年、フォン・ノイマンによって考案された。

1. アルゴリズム
---------

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

データ列を分割する
分割された各データ列で、含まれるデータが1個ならそれを返し、2個以上ならステップ1から3を再帰的に適用してマージソートする
二つのソートされたデータ列をマージするステップ1と2の途中についてこのアルゴリズムの手順に含めず、あらかじめ局所的に整列されている多数の列が与えられるもの、とすることもある。後述する、テープをマージする手法の場合、最初のテープから主記憶を可能な限り全部使って整列できるだけ整列した部分列を、順次書き出したテープから始める。

ステップ3のマージでは、2本のデータ列の先頭同士を比べ小さい方をデータ列から取り出して出力し、残りのデータをもつ2本のデータ列に対して再帰的に同じ処理を、両方が空になるまで行う。ソートすべきデータ列が部分的に順次得られる場合、オンラインアルゴリズムとして、部分データ列をソートして後でマージするという変形も可能である。

クイックソート等と同様、完全に細分化せずにスレッショルドとして適度に大きい個数を設定し、それ以下になった時点でなんらかの「ごく少数の対象専用の高速なコードによるソート」を併用するという高速化手法がある。手順として書き出すと次のようになる。

データ列を分割する
分割された各データ列で、含まれるデータが設定個数以下ならそれを別の高速なアルゴリズムでソートして返し、設定個数超ならステップ1から3を再帰的に適用してマージソートする
二つのソートされたデータ列をマージする他に特殊な応用例として、外部ソートの1手法でテープに収められたデータをソートする、というものがある。最も単純な、4本のテープを2本ずつ使う「平衡2系列マージ」を例に説明する。まず元のデータから、利用可能な内部記憶をできるだけ使って、部分的に整列されている列をテープに書き出す。この時、2本のテープに交互に書き出すようにする。

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

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

1.1. 実装例
--------

1.1.1. C
--------

include void merge { int i = left; int j = mid; int k = 0; int l; while  { if  { B[k++] = A[i++]; } else { B[k++] = A[j++]; } } if  { /* i側のAをBに移動し尽くしたので、j側も順番にBに入れていく */ while  { B[k++] = A[j++]; } } else { while  { /* j側のAをBに移動し尽くしたので、i側も順番にBに入れていく */ B[k++] = A[i++]; } } for  { A[left + l] = B[l]; } } void merge_sort { int mid; if  { return; } mid =  / 2; merge_sort; merge_sort; merge; } int main { int a[10] = {8,4,7,2,1,3,5,6,9,10}; int b[10] = {0}; const int n = 10; int i; merge_sort; for  { printf; } printf; }<WtXmlEndTag />

1.1.2. Ruby
-----------

def mergesort lst return _mergesort_ lst.dup # 副作用で配列が壊れるので、複製を渡す end

def _mergesort_ lst if  <= 1 then return lst end

pop メソッドの返す値と副作用の両方を利用して、lst を二分するlst2 = lst.pop

return _merge_, _mergesort_) end

def _merge_ lst1, lst2 len1, len2 = lst1.size, lst2.size result = Array.new 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<WtXmlEndTag />

1.1.3. Haskell
--------------

mergesort :: Ord t => [t] -> [t] mergesort lst = case lst of [] -> lst [_] -> lst _ -> merge   where  = split lst

merge [] [] = [] merge xxs [] = xxs merge [] yys = yys merge xxs@ yys@ | x < y = x :  | otherwise = y : 

split [] =  split ~ =  where  = split xs<WtXmlEndTag />

1.1.4. Scheme
-------------

; use-modules は 処理系 Guile 固有の機能である。; SRFI 機能を使うための仕組み処理系に依る。) ; split-at ) ; let-values

   ))   ls))   rs)) ) ))   rs )  )))))))

  xs) ) xs)   2))))  )))))<WtXmlEndTag />

2. アルゴリズムの動作例
-------------

初期データ: 8 4 3 7 6 5 2 1

データ列を二分割する。 8 4 3 7 | 6 5 2 1
もう一度、二分割する。 8 4 | 3 7 | 6 5 | 2 1
各データ列にデータ数が2以下になったところで、各データ列内のデータをソートする。 4 8 | 3 7 | 5 6 | 1 2
この例の場合は、右2つのデータ列、左2つのデータ列をそれぞれマージとソートし、2つのデータ列にする。 3 4 7 8 | 1 2 5 6
2つのデータ列をマージとソートする。 1 2 3 4 5 6 7 8

3. 脚注
-----

4. 関連項目
-------

マージ

5. 外部リンク
--------

[1]

no:Sorteringsalgoritme#Flettesortering