マージソート

説明

mergesort は数列 a = [a_0, ..., a_{n-1}] が与えられたとき，これをソートする．

アルゴリズムは次のとおり．まず数列を真ん中で二つに分ける．それぞれを再帰的にソートし，結果をマージする．マージは二つに分けたそれぞれの列から，小さいものを一つづつ取り出すことで行われる．計算量は T(n) = 2 T(n/2) + O(n) なので最良時も最悪時も変わらず O(n log n) である．

上記アルゴリズムをナイーブに実装すると外部に記憶容量を O(n) で持つことになる．これに対してインプレースマージと呼ばれる，マージを列の中の入れ替えで実現する手法によって外部記憶を省略することができる．しかし実用上はこの手法は速度を低下させるため，取られることは少ない．

マージソートは安定なソートである．すなわち比較によって順位がつかない要素の並び順はソート前後で保存される．マージソートは安定なソートの中で最も扱いやすいものの一つなので，実用上にも重要である．

なお，通常安定なソーティングには std::stable_sort を使えば十分である．このアルゴリズムを記載したのは，例えばバブルソートの交換回数を求めるアルゴリズムのように，要素の大小の並びに関するアルゴリズムのテンプレートのためである．

計算量

• O(n log n)．

ソースコード

void mergesort(vector<int> &a) {
  int n = a.size();
  if (n > 1) {
    vector<int> b(a.begin(), a.begin() + n/2);
    vector<int> c(a.begin() + n/2, a.end());
    mergesort(b);
    mergesort(c);
    for (int i = 0, j = 0, k = 0; i < n; ++i)
      if (k == c.size())      a[i] = b[j++];
      else if (j == b.size()) a[i] = c[k++];
      else if (b[j] < c[k])   a[i] = b[j++];
      else                    a[i] = c[k++];
  }
}

Verified