整列アルゴリズムを比較する(マージソート編)

どうも、マジでまじい(不味い)マージポテートです(?)
いや僕は食べ物じゃないｗ

前回は手抜きヒープソート編でした。

ということで今回はマージソート編です。

マージソートとは、配列を分解して、それを結合させながら行う整列アルゴリズムです。
例えば{3,2,5,9,1,4}は
1. 3,2,5と9,1,4に分ける
2. 3,2と5と9,1と4に分ける
3. 3,2,5,9,1,4がバラバラになる
4. まとめる2,3   5   1,9   4
5. まとめる2,3,5   1,4,9
6. まとめる1,2,3,4,5,9

ということで、C++プログラムにしていきます。
これを読む前に、交換法編、クイックソート編を見ておくといいです。(ここでは省略した説明が書いてあります。)

void marge(int array[],int array_size){
    struct func{
        int *array,array_size;
        void marge(int st,int mid,int en){
            int sn=mid-st,enn=en-mid;
            int S[sn+1],E[enn+1];
            copy(&array[st],&array[mid+1],S);
            copy(&array[mid],&array[en+1],E);
            S[sn]=INT_MAX;
            E[enn]=INT_MAX;
            int i=0,j=0;
            for(int k=st;k<en;k++){
                if(S[i]<=E[j]){
                    array[k]=S[i];
                    i++;
                }else{
                    array[k]=E[j];
                    j++;
                }
            }
        }
        void sort(int st,int en){
            if(st+1<en){
                int mid=(st+en)/2;
                sort(st,mid);
                sort(mid,en);
                marge(st,mid,en);
            }
        }
    };
    struct func a;
    a.array=array;
    a.array_size=array_size;
    a.sort(0,array_size);
}

marge関数は結合、sort関数は分解を行います。
sort関数には最初のインデックスと最後のインデックスを渡します。
if文でまだ分解できるかどうかを判断し、変数midを中心として分解し、またsort関数に渡して再帰処理を行います。
そして最後にmarge関数に渡して結合します。
marge関数には、最初、中間、最後のインデックスを渡します。
配列の内容が変わっていくので、配列Sに最初側、Eに最後側をコピーします。インデックスを一つ余分に宣言し、配列の最後にint型での最大値を入れておきます。
結合をする2つのまとまりはそれぞれの中で既に整列済みであるので、配列S,Eを並行に順番で読んでいきます。最後の要素として表現できる最大値を代入したのは、インデックスの最大値の制御を省略するためです。

ということで、マージソートの完成です!
これで今回作る全ての整列アルゴリズムが完成しました～、次回はいよいよ比較編です!