tomboのブログ

競技プログラミングのことをいろいろ書きます AtCoder A茶H水

マージソートを、書きます。

tomboです。マージソートを、書きます。(書くので)

安定して速いです

マージソートは安定ソートで、ソートしたいデータ数  N に対して最悪ケースの時間計算量が  O(NlogN) です。例えばクイックソートは不安定ソートで、ピボットの選び方によってはマージソートより遅く  (O(N^2)) なったりします。色々な言語のソート関数でも、内部でマージソートが実装されているんじゃないかなーと思っています。(思っているだけ)

実装の方針

分割統治法をします。「困難は分割せよ」の精神で (DP的な) 、分割してソートしながらマージしていって、最終的に全体のソートを達成します。分割は二分木のようにします。今回は再帰関数を使います。(他の実装をしらない←)

二分木の高さは、要素数 N として  O(logN) になるので、マージの処理には  O(N) かけても、全体で  O(NlogN) になることが分かります。そして、再帰的にマージするときの一番のポイントが、マージするたびに要素がソートされるということです。

問題と実装

verifyにはこの問題を使いました。
アルゴリズムと数学 演習問題集 027 - Sorting

提出
https://atcoder.jp/contests/math-and-algorithm/submissions/52793571

再帰関数の説明をします。
まず、左右に分けながら帰りがけ再帰をします。

vector<ll> left, right;
ll n = v.size();

// 左半分
rep(i, 0, n/2){
    left.push_back(v[i]);
}
// 右半分
rep(i, n/2, n){
    right.push_back(v[i]);
}

// 左右それぞれ帰りがけ再帰
vector<ll> v1, v2;
if (left.size()>=2){
    v1 = merge_sort(left);
} else {
    v1 = left;
}
if (right.size()>=2){
    v2 = merge_sort(right);
} else {
    v2 = right;
}

このとき、木の高さは  O(logN) なので、配列長が  O(N) であっても、これらの操作は間に合うことが分かります。( 1 \leq N \leq 10^5 くらいの入力の大きさを仮定しています)
素数が1になったら、そこからマージしながらreturnします。

ll i1 = 0;
ll i2 = 0;
ll n1 = v1.size();
ll n2 = v2.size();
vector<ll> ret;
while (true){
    // 両方のインデックスがsize()未満のとき
    if (i1<n1 && i2<n2){
        // 小さい方の値をretに入れる
        if (v1[i1]<=v2[i2]){
            ret.push_back(v1[i1]);
            i1++;
        } else {
            ret.push_back(v2[i2]);
            i2++;
        }
    }
    // 片方だけのときはそのまま入れる
   else if (i1<n1){
        ret.push_back(v1[i1]);
        i1++;
    }
    else if (i2<n2){
        ret.push_back(v2[i2]);
        i2++;
    }
    // 両方の値を見終わったらbreak
    else {
        break;
    }
}

return ret;

マージは、左右の配列のインデックスを進めていきながら、小さい方をretに入れていきました。ここで  O(N) でソートされた配列を構成できるのは、マージ前にすでにそれらの配列がソートされているためです。


帰りがけ再帰なので、まず再帰の一番深いところ(要素数が1)のところまで降りてから  ( O(logN) )、戻りながらマージして  ( O(N) )、マージ後には値がソートされているわけなので、  O(NlogN) でソートを達成することができました。

まとめ

分割統治法は、細かく問題を分割してそれぞれ解いてからマージするという手法です。ソート以外にも使い方があると思うので、調べてみて下さい。自分も、いつか分割統治+FFTを理解します(いつか)