アルゴリズムとデータ構造：マージソート - デラエモン、カイハツニッキ

クイックソートは元データの並びが悪いとバブルソートと同じくらい効率が悪い。
もっと確実に効率の良い方法はないかということでマージソートがありますよ、と。
クイックソートよりも最悪計算量が少ない。

[マージソートの計算量]
最悪：O(N Log N)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 8 /* データ件数 */

int sort[N];
int buffer[N];
int count; /* 交換回数 */
void MergeSort(int n, int x[]);
void output(int list[],int j,char *name);

void MergeSort(int n, int x[]) {
    int i, j, k, m;

    if(n <= 1){ 
        return; 
    }   
    m = n / 2;

    /* ブロックを前半と後半に分ける */
    MergeSort(m, x); 
    MergeSort(n - m,x + m); 

    /* 併合（マージ）操作 */
    for(i = 0; i < m; i++){
        buffer[i]  = x[i];
    }   
    output(buffer,i,"buffer");
    output(x+m,m,"x");

    j = m;
    i = k = 0;

    while(i < m && j < n){ 
        if(buffer[i] <= x[j]){
            x[k++] = buffer[i++];
        }
        else{
            x[k++] = x[j++];
        }
        output(sort,N,"sort");
        ++count;
    }

    while(i < m){
        x[k++] = buffer[i++];
        output(sort,N,"sort");
    }

    printf("-- result --\n");
    output(sort,N,"sort");
    printf("\n");
}

int main(void){
    int i;
    clock_t start,end;

    srand((unsigned int) time (NULL));

    printf("Standby...\n");

    for(i = 0; i < N; i++){
        /* ランダムな数値を格納 */
        sort[i] = rand() % 10 + 1;
    }
    output(sort,N,"sort");

    printf("\n<< Start >>\n");
    start = clock();

    MergeSort(N, sort);

    end = clock();
    printf("\n<< End >>\n");
    output(sort,N,"sort");
    printf("Count:%d\n",count);
    printf("Time:%.2f\n",(double)(end-start)/CLOCKS_PER_SEC);

    return EXIT_SUCCESS;
}

データ件数8件、1〜10の乱数を発生させて実行した結果

$ ./merge_sort
Standby...
sort => [6,10,4,8,2,6,7,5]

<< Start >>
buffer => [6]
x => [10]
sort => [6,10,4,8,2,6,7,5]
-- result --
sort => [6,10,4,8,2,6,7,5]

buffer => [4]
x => [8]
sort => [6,10,4,8,2,6,7,5]
-- result --
sort => [6,10,4,8,2,6,7,5]

buffer => [6,10]
x => [4,8]
sort => [4,10,4,8,2,6,7,5]
sort => [4,6,4,8,2,6,7,5]
sort => [4,6,8,8,2,6,7,5]
sort => [4,6,8,10,2,6,7,5]
-- result --
sort => [4,6,8,10,2,6,7,5]

buffer => [2]
x => [6]
sort => [4,6,8,10,2,6,7,5]
-- result --
sort => [4,6,8,10,2,6,7,5]

buffer => [7]
x => [5]
sort => [4,6,8,10,2,6,5,5]
sort => [4,6,8,10,2,6,5,7]
-- result --
sort => [4,6,8,10,2,6,5,7]

buffer => [2,6]
x => [5,7]
sort => [4,6,8,10,2,6,5,7]
sort => [4,6,8,10,2,5,5,7]
sort => [4,6,8,10,2,5,6,7]
-- result --
sort => [4,6,8,10,2,5,6,7]

buffer => [4,6,8,10]
x => [2,5,6,7]
sort => [2,6,8,10,2,5,6,7]
sort => [2,4,8,10,2,5,6,7]
sort => [2,4,5,10,2,5,6,7]
sort => [2,4,5,6,2,5,6,7]
sort => [2,4,5,6,6,5,6,7]
sort => [2,4,5,6,6,7,6,7]
sort => [2,4,5,6,6,7,8,7]
sort => [2,4,5,6,6,7,8,10]
-- result --
sort => [2,4,5,6,6,7,8,10]


<< End >>
sort => [2,4,5,6,6,7,8,10]
Count:16
Time:0.00

データ件数を100000000にして実行しても1分弱で
クイックソートのときよりも多い件数でもちゃんと計算できた。
ログが上手く吐けなく前回から随分日が経ってしまった。
x[k++]の挙動を考えれば当たり前なのですが、すぐ気付けなかった。
x[k++] = buffer[i++];ってやってる箇所の直線で
printf("x[%d]:%d = buffer[%d]:%d",k++,x[k++],i++,buffer[i++]);とかやっちゃって。
そりゃもう、結果もめちゃくちゃですよねえ。
これでやっと次に行ける。