Version 13.19
マージソートのコーディング

「前回は、マージソートの仕組みについて説明しました」
『ってことは今回はコードね』
「というわけで、マージソートの関数です」

void DoMergeSort( int *p_piAry, int p_iSize )
{
    // Ａ
    if( p_iSize <= 1 )
    {
        // 要素数が１以下なら何もしません。
        return;
    }

    // Ｂ
    // 中央から左側のサイズを取得します。
    int iLeftSize = p_iSize / 2;
    // 中央から右側のサイズを取得します。
    int iRightSize = p_iSize - iLeftSize;
    // 中央から左側のサイズの配列を作成します。
    int *piLeftAry = new int[iLeftSize];
    // 中央から右側のサイズの配列を作成します。
    int *piRightAry = new int[iRightSize];
    // それぞれコピーします。
    int iF1;
    for( iF1 = 0; iF1 < iLeftSize; ++iF1 )
    {
        piLeftAry[iF1] = p_piAry[iF1];
    }
    
    for( iF1 = 0; iF1 < iRightSize; ++iF1 )
    {
        piRightAry[iF1] = p_piAry[iLeftSize + iF1];
    }

    // Ｃ
    // それぞれ再帰呼び出しします。
    DoMergeSort( piLeftAry, iLeftSize );
    DoMergeSort( piRightAry, iRightSize );

    // Ｄ
    // マージします。
    int iLeftPos = 0;
    int iRightPos = 0;
    while(
        ( iLeftPos  < iLeftSize  ) || 
        ( iRightPos < iRightSize )
        )
    {
        // 左右両方とも配列の中にいる間、ループします。

        if( iRightSize <= iRightPos )
        {
            // 右側が配列の最後まで来ている場合。
            // 左側を追加します。
            p_piAry[iLeftPos + iRightPos] = piLeftAry[iLeftPos];
            ++iLeftPos;
        }
        else if( iLeftSize <= iLeftPos )
        {
            // 左側が配列の最後まで来ている場合。
            // 右側を追加します。
            p_piAry[iLeftPos + iRightPos] = piRightAry[iRightPos];
            ++iRightPos;
        }
        else if( piLeftAry[iLeftPos] > piRightAry[iRightPos] )
        {
            // 左側の方が右側より大きい場合。
            // 右側を追加します。
            p_piAry[iLeftPos + iRightPos] = piRightAry[iRightPos];
            ++iRightPos;
        }
        else
        {
            // それ以外の場合（左側の方が右側より小さい場合）。
            // 左側を追加します。
            p_piAry[iLeftPos + iRightPos] = piLeftAry[iLeftPos];
            ++iLeftPos;
        }
    }

    // Ｅ
    // 解放します。
    delete[] piLeftAry;
    delete[] piRightAry;
}

『長！』
「使用例はこちら」

void Use_DoMergeSort()
{
    int iAry[5];
    iAry[0] = 4;
    iAry[1] = 9;
    iAry[2] = 3;
    iAry[3] = 5;
    iAry[4] = 8;

    // ソートします。
    DoMergeSort( iAry, 5 );

    for( int iF1 = 0; iF1 < 5; ++iF1 )
    {
        TRACE( "%d ", iAry[iF1] );
    }
    TRACE( "\n" );
    // 3 4 5 8 9 
}

『使い方は普通ね』
「それでは、少しずつ見ていきます。まずＡ〜Ｂ」
『サイズが 1 以下だったら return ……いきなり関数終了しているね』
「これはあとで説明します」
『いきなりかい！』
「というわけで次、Ｂ〜Ｃ」
『長さ取って長さ取って、 new して new して、 for して for して』
「ここは〈分割〉フェーズ。前回の例で説明するね」

4 9 3 5 8 

「このデータを、前回はいっぺんにバラバラにしたけど、実際のプログラム
ではふたつずつに分けて、 new で作った配列にコピーしていきます」
『サイズを 2 で割って左右のサイズを出すわけね。なんかクイックソート
に似てる……』
「分割してコピー、をイメージするとこんな感じかな」

(4,9) (3, 5, 8)
 4  9  3  5  8 

「 () で囲んだところが new で作った動的配列」
『左右 new で作って、そこに for でループして１個ずつコピーするわけ
ね』
「このコピーが終わったら、次は再帰呼び出し」
『 Version 13.16 ( No.252 ) のアレね。自分の関数をもう一度呼ぶって
ゆー。あ、ってことは』

    // それぞれ再帰呼び出しします。
    DoMergeSort( piLeftAry, iLeftSize );
    DoMergeSort( piRightAry, iRightSize );

『のとこがそうね』
「そう、このＣ〜Ｄの箇所でもう一度自分自身を呼びます。この呼び出しは
さっき分割したそれぞれに対して。つまり」

(4,9) 
(3, 5, 8)

「このふたつ別々に呼び出します」
『呼び出すと？』
「また分割。たとえば上のだと」

(4) (9)＜分割後
(4 , 9)＜分割前

「というふうに分けられます。さらにこれが」
『再帰呼び出しで呼ばれる』
「すると、たとえば (4) は、サイズが 1 だから」
『あ、Ａ〜Ｂの if で引っかかるね』
「そういうこと。 (9) も同様。なので、 (4) (9) の場合、Ｃ〜Ｄの再帰呼
び出しをすると、何もせずにすぐに返ってきます」
『そこでＤ〜Ｅね』
「この while のループはマージ箇所。

(4) (9)＜分割後
(4 , 9)＜分割前

「この〈分割後〉の方を小さい順に〈分割前〉へとコピーしていきます。 
まず、while は、分割したふたつの配列を全部チェックする、っていう
ループ」
『ふたつチェックしてるね』
「で、そのループの中で４つの if でチェックしてます。最初のふたつの 
if は〈片方がマージし終えてたら、もう片方のを無条件に入れる〉ってい
う簡単な話」
『？』
「前回の例で言うと

(9)
()
　↓
[3,4,5,8,]

「この状態のこと。下の () にはもうマージする数が存在しないから」
『何も考えずにもう片方の (9) からマージしちゃえ、ってことね』
「そういうこと。残りのふたつは単純な比較」

(9)
(8)
　↓
[3,4,5,,]

「という状態の時に、小さい方をマージする、っていうこと」
『４つ if があるけど、上２つと下ふたつに分かれてる感じね』
「このマージを繰り返していけば、ふたつの分割した配列が元の配列にマー
ジされます」
『あ、そか、引数で渡されてる配列にマージしてるんだね』
「そう。だから、最終的には」
『ソート元の配列にマージされるわけね』
「そういうこと。最後に、分割したときに作った配列を解放して、１段階完
了」
『これを繰り返して完全にマージ完了、ね』

/*
    Preview Next Story!
*/
『って説明されるとわかるんだけどねー』
「実際に作れない？」
『作れない作れない』
「というわけで、使うだけのバージョンを用意しました」
『おー』
「というわけで次回」
＜ Version 13.20 マージソート・汎用版 ＞
『につづく！』
「でもいつかは作れるようにね」
『無理です』