マージソート

マージソート
	マージソートの例。まずリストを小さな単位に分け、二つのリストをそれぞれの要素の先頭を比較してマージする。最後までこの操作をくり返すと、リストはソートされている。
クラス	ソート
データ構造	配列
最悪計算時間
最良計算時間	typical, natural variant
平均計算時間
最悪空間計算量	外部記憶

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

n個のデータを含む配列をソートする場合、最悪計算量 O(n log n)である。分割と統合の実装にもよるが、一般に安定なソートを実装できる。インプレースな（すなわち入力の記憶領域を出力にも使うので、追加の作業記憶領域を必要としない）バリエーションも提案されているが、一般には、O(n)の追加の作業記憶領域を必要とする^[1]。

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

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

アルゴリズム

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

データ列を分割する（通常、二等分する）
分割された各データ列で、含まれるデータが1個ならそれを返し、2個以上ならステップ1から3を再帰的に適用してマージソートする
二つのソートされたデータ列（1個であればそれ自身）をマージする

ステップ1と2の途中（すなわち細分化するまでの部分）についてこのアルゴリズムの手順に含めず、あらかじめ局所的に整列されている多数の列が与えられるもの、とすることもある。後述する、テープをマージする手法の場合、最初のテープから主記憶を可能な限り全部使って整列できるだけ整列した部分列を、順次書き出したテープから始める。

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

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

データ列を分割する（通常、二等分する）
分割された各データ列で、含まれるデータが設定個数以下ならそれを別の高速なアルゴリズムでソートして返し、設定個数超ならステップ1から3を再帰的に適用してマージソートする
二つのソートされたデータ列をマージする

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

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

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

実装例

C

#include <stdio.h>
void merge(int A[], int B[], int left, int mid, int right) {
    int i = left;
    int j = mid;
    int k = 0;
    int l;
    while (i < mid && j < right) {
        if (A[i] <= A[j]) {
            B[k++] = A[i++];
        } else {
            B[k++] = A[j++];
        }
    }
    if (i == mid) { /* i側のAをBに移動し尽くしたので、j側も順番にBに入れていく */
        while (j < right) {
            B[k++] = A[j++];
        }
    } else {
        while (i < mid) { /* j側のAをBに移動し尽くしたので、i側も順番にBに入れていく */
            B[k++] = A[i++];
        }
    }
    for (l = 0; l < k; l++) {
        A[left + l] = B[l];
    }
}
void merge_sort(int A[], int B[], int left, int right) {
    int mid;
    if (left == right || left == right - 1) { return; }
    mid = (left + right) / 2;
    merge_sort(A, B, left, mid);
    merge_sort(A, B, mid, right);
    merge(A, B, left, mid, right);
}
int main(void) {
    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(a, b, 0, n);
    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

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

Scheme

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

(define (merge left-half right-half)
  (let loop ((ls left-half) (rs right-half) (result (list)))
    (cond
      ((null? rs) (append (reverse result) ls))
      ((null? ls) (append (reverse result) rs))
      (else
        (let ((l (car ls)) (r (car rs)))
          (if (<= l r)
            (loop (cdr ls) rs (cons l result))
            (loop ls (cdr rs) (cons r result))))))))

(define (merge-sort xs)
  (cond
    ((null?      xs ) xs)
    ((null? (cdr xs)) xs)
    (else
      (let-values
        (((left-half right-half)
          (split-at xs (quotient (length xs) 2))))
        (merge
          (merge-sort left-half)
          (merge-sort right-half))))))

アルゴリズムの動作例

初期データ: 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

脚注

^ ^a ^b ^c 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、267頁。ISBN 4-87408-414-1。
^ Knuth, Donald (1998). “Section 5.2.4: Sorting by Merging”. Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Addison-Wesley. pp. 158. ISBN 0-201-89685-0

外部リンク

マージソートコード(英語)

[algo-1] 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、267頁。ISBN 4-87408-414-1。

[2] Knuth, Donald (1998). “Section 5.2.4: Sorting by Merging”. Sorting and Searching. The Art of Computer Programming. 3 (2nd ed.). Addison-Wesley. pp. 158. ISBN 0-201-89685-0

[1]

[2]