マージソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

このページでは「マージソート」について解説し、さらにC言語でマージソートを実装したプログラムと、そのプログラムの解説をしていきたいと思います。

マージソートとは

マージソートとはソートのアルゴリズムの１つです。

下のページで「クイックソート」について解説しましたが、

クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

このクイックソートに比べると、このページで紹介するマージソートには下記のような特徴があります。

• クイックソートに比べて処理速度が安定している
• クイックソートに比べて使用メモリ量が多い

マージソートの考え方

マージソートは、与えられたデータの集合を下記の考え方によってソートするアルゴリズムになります。

• 集合を中央で２つに分割する
• 分割後の各集合のデータをそれぞれソートする
• ソート済みの各集合の小さいデータから順に新しい集合にコピーしてマージする

文だけだとちょっと分かりにくいので、図を使って補足していきます。

まずソートしたいデータの集合を中央で分けて２つの集合を作成します。

そして、この２つの集合それぞれをソートします（今回は昇順にソート）。

さらに、この２つの集合の小さいデータから順に新しい集合にコピーしていくことでマージします。

で、ここでおそらく皆さんが疑問を抱くのが下記の２つだと思います。

• ２つの集合をマージするって具体的にどうするの？
• そもそも各集合をどうやってソートするの？

これらについて、ここから集合のマージと分割した集合のソートの節で解説していきたいと思います！

スポンサーリンク

集合のマージ

マージソートの１番のポイントは「ソート済みの各集合をマージする」ところです。

マージとは「結合する」「合体する」「併合する」などの意味を持つ言葉です。

ただし、単純に２つの集合をマージするだけだとデータ全体がソートされたことにはなりませんので、データ全体をソートするためには、小さい or 大きい順にデータをマージしていく必要があります。

マージソートにおいては、すでに２つの集合それぞれがソート済みなので、２つの集合の先頭のデータを比較するだけで（より正確にいうと２つの集合の “まだマージされていない” 先頭のデータを比較するだけで）、小さい or 大きい順にデータをマージできるところがポイントになります。

この辺りは実例で確認していくと分かりやすいと思います！

ということで、下図の “昇順にソート済み” の２つの集合をマージすることで、データ全体が昇順にソートがされる様子を図を使って確認していきましょう。

まず２つの集合の中から一番小さいデータを決定し、そのデータをマージ先の集合の先頭データとします。

２つの集合はそれぞれ昇順にソート済みですので、一番小さいデータの候補は「ぞれぞれの集合における先頭のデータの２つ」になります。

そして、この２つのデータの小さい方が、２つの集合の中で一番小さいデータとなります。

この一番小さいデータをマージ先の集合の先頭のデータとします。

次は２つの集合の中から２番目に小さいデータを決定し、そのデータをマージ先の集合の２番目のデータにします。

一番小さいデータはすでにマージ済みということを考えると、２つの集合の “まだマージされていないデータ” の中から一番小さいデータを決定することになります。

つまり、２番目に小さいデータの候補は「”マージ済みのデータを取り除いた” ぞれぞれの集合における先頭のデータの２つ」になります（これは、各集合それぞれが昇順にソート済み＆一番小さいデータは” マージ済み” だからです）。

そして、この２つのデータの小さい方が、２つの集合の中で２番目に小さいデータとなります。

この２番目に小さいデータを、マージ先の集合の２番目のデータとしてマージします。

同じ感じで、集合の “マージ済みでない”  先頭のデータ同士の比較とマージを繰り返していきます。次は下の図のようにマージされ、

その次は下の図のようにマージされていきます。

全データがマージされればマージは終了します。今回の例の場合は、最後は下の図のようにマージされることになります。

図を見ていただければ分かるとおり、この手順でマージを行っていくと、マージ先の集合は２つの集合のデータをソートした結果となります。

これはこの例に限った話ではありません。

この手順でマージを行うと、マージを行う２つの集合がソートさえされていれば、必ずマージ先の集合は２つの集合の全データがソートされた状態になります。

これはいろんなデータで試していただくと実感していただけると思います。

つまり、ソートしたいデータの全体を２つにまず分割し、その分割した各々の集合のデータをソートしてやれば、後は上記の手順で２つの集合のデータをマージすることによりデータ全体をソートすることが可能です。

マージソートはこの考えに則ってデータをソートするアルゴリズムになります。

分割した集合のソート

上記によって、ソートされた２つの集合をマージすることでデータ全体がソートされることになることは理解していただけたのではないでしょうか？

ただし、これを行うためには当然「２つの集合それぞれがソートされている」ことが前提になります。

では、２つに分割した集合それぞれはどのようにしてソートすれば良いでしょうか？

マージソートです！

要は、２つに分割した集合それぞれを “新たなデータ全体” として、それぞれに対してマージソートを行うことでソートを行えば良いです（つまり、マージソートの中でマージソートを再帰的に実行します）。

下記のようにデータの全体を２つに分割したとしましょう。

それぞれの集合をマージソートでソートすることを考えます。

マージソートとはデータの集合を下記の考え方でソートするソート方法でしたね。

• 集合を中央で２つに分割する
• 分割後の各集合のデータをそれぞれソートする
• ソート済みの各集合の小さいデータから順に新しい集合にコピーしてマージする

この考え方の通り、まずは各集合は下の図のように２つずつに分割します。

そして分割後の集合をソートします。このソートにもマージソートを用います。

つまり、さらにこの２つの集合を分割することになります。分割してみましょう！

すると、下の図のように各集合に存在するデータが１つになります。

ここで注目していただきたいのが、分割後の各集合内のデータの並びです。

集合に存在するデータが１つなので実感が湧かないかもしれませんが、集合内のデータは実はソートされていることが分かりますか？各集合内のデータ全体が昇順（or 降順）に並んでますよね？

つまり、データ数が１つの集合は、データが１つなのでソート済みであると考えることできます。

こんな感じで集合に存在するデータが１つになるまでマージソートを繰り返し行うことで、最終的に分割された集合のデータが自動的にソートされることになります。

集合のデータがソートされれば、もうその集合のソートを行う必要はありません。

続いて集合のマージで説明した手順に基づいて「ソート済みの各集合をマージする」が行われることになります。

上の図の８つの集合は下の図のように２つずつマージされて４つの集合にマージされることになります。

これによりマージ後の４つの集合もソートされたことになりますので、さらにこれらの４つの集合を２つずつマージします。

これで、最初に分割した２つの集合がそれぞれソートされたことになりますね。

こんな感じで、マージソートを（再帰的に）繰り返して集合のデータ数が１つになるまで分割を繰り返します。

そしてその後、ソート済みの集合を２つずつマージしながら集合をどんどんマージしていくことで、最終的には最初に分割した集合までソートされることになります。

マージソートのプログラム

ここまで説明してきたマージソートをC言語で実装したプログラムが下記になります。

#include <stdio.h>
#include <stdlib.h> /* memcpy用 */

/* データの数 */
#define NUM 10

/* 配列のデータを表示する関数 */
void printArray(int a[], int num){
    int i;
    for (i = 0; i < num; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

/* ２つの集合をマージする関数
 * data[] : マージを行うデータの集合
 *         (マージ後のデータの集合を格納)
 * left : マージする１つ目の集合範囲の開始点
 * mid : マージする１つ目の集合の範囲の終了点
 * right : マージする２つ目の集合の範囲の終了点
 * work[] : マージを行うために必要な作業メモリ
 *          (マージ先集合として一時退避先として使用)
 */
void merge(int data[], int left, int mid, int right, int work[]){
    int i, j, k, size;

    /* １つ目の集合の開始点をセット */
    i = left;

    /* ２つ目の集合の開始点をセット */
    j = mid + 1;

    /* マージ先集合の開始点をセット */
    k = 0;

    /* ２つの集合のどちらかが全てマージ済みになるまでループ */
    while (i <= mid && j <= right) {
        /* マージ済みデータを抜いた２つの集合の
           先頭のデータの小さい方をマージ */
        if (data[i] < data[j]) { 
            work[k] = data[i];
            /* マージした集合のインデックスと
               マージ先集合のインデックスをインクリメント */
            i++;
            k++;
        } else {
            work[k] = data[j];
            /* マージした集合のインデックスと
               マージ先集合のインデックスをインクリメント */
            j++;
            k++;
        }
    }

    /* マージ済みでないデータが残っている集合を
       マージ先集合にマージ */
    while (i <= mid) {
        work[k] = data[i];
        i++;
        k++;
    }
    while (j <= right) {
        work[k] = data[j];
        j++;
        k++;
    }

    /* マージ先集合のサイズを計算 */
    size = right - left + 1;

    /* マージ先集合をdataにコピー */
    memcpy(&data[left], work, sizeof(int) * size);
}

/* マージソートを行う関数
 * data[] : ソートを行うデータの集合
 *          (ソート後のデータの集合を格納)
 * left : ソートを行う範囲の開始点
 * right : ソートを行う範囲の終了点
 * work[] : ソートを行うために必要な作業メモリ
 */
void mergeSort(int data[], int left, int right, int work[]) {
    int mid;


    /* データ数が１の場合はソート済みなのでソート終了 */    
    if (left == right) {
        return;
    }

    /* 集合を中央で２つに分割する */
    /* left 〜 mid の集合と
        mid+1 〜 right の集合に分割 */
    mid = (left + right) / 2;

    /* 分割後の各集合のデータをそれぞれソートする */
    mergeSort(data, left, mid, work);
    mergeSort(data, mid + 1, right, work);

    /* ソート済みの各集合をマージする */
    merge(data, left, mid, right, work);
}

/* 配列を初期化する関数 */
void initArray(int a[])  {
    a[0] = 5;
    a[1] = 0;
    a[2] = 9;
    a[3] = 7;
    a[4] = 1;
    a[5] = 6;
    a[6] = 3;
    a[7] = 8;
    a[8] = 4;
    a[9] = 2;
}

int main(void)  {
    int array[NUM];
    int work[NUM];

    /* 配列を初期化 */
    initArray(array);

    /* ソート前の配列の表示 */
    printArray(array, NUM);

    /* マージソート */
    mergeSort(array, 0, NUM - 1, work);

    /* ソート後の配列の表示 */
    printArray(array, NUM);

    return 0;
}

スポンサーリンク

プログラムの解説

最後にプログラムの解説を行います。が、ほぼマージソートとはで解説した内容をプログラミングしているだけ＆必要な分はコメントを記載していますので、ここではポイントだけ説明しておきます。

mergeSort 関数

mergeSort 関数で主に行っているのはマージソートとはで紹介した下記の３つです。

• 集合を中央で２つに分割する
• 分割後の各集合のデータをそれぞれソートする
• ソート済みの各集合の小さいデータから順に新しい集合にコピーしてマージする

この３つは mergeSort 関数内のコメントでも記述していますので、解説と関数の処理を照らし合わせて見ていただければ、何をしているのかを理解していただけると思います。

分割後の各集合のソートはマージソートで行っていますので、mergeSort 内でさらに分割した２つの集合に mergeSort 関数を実行しています（再帰呼び出し）。

/* 分割後の各集合のデータをそれぞれソートする */
mergeSort(data, left, mid, work);
mergeSort(data, mid + 1, right, work);

またソートを行うデータ数が１つになった際にはソートが完了したことになりますので、この際には関数の先頭で return を実行して関数を終了するようにしています。

/* データ数が１の場合はソート済みなのでソート終了 */    
if (left == right) {
    return;
}

merge 関数

マージは２つのデータの集合に対し、下記のように処理を行っています。

• 一方のデータの集合が空になるまでマージを行う
• 一方のデータが空になったら、他方のデータを、そのデータ順でそのままマージ先集合にコピー

前者を行っているのは下記部分で、

/* ２つの集合のどちらかが全てマージ済みになるまでループ */
while (i <= mid && j <= right) {
    /* マージ済みデータを抜いた２つの集合の
       先頭のデータの小さい方をマージ */
    if (data[i] < data[j]) { 
        work[k] = data[i];
        /* マージした集合のインデックスと
           マージ先集合のインデックスをインクリメント */
        i++;
        k++;
    } else {
        work[k] = data[j];
        /* マージした集合のインデックスと
           マージ先集合のインデックスをインクリメント */
        j++;
        k++;
    }
}

後者を行っているのは下記部分になります。

/* マージ済みでないデータが残っている集合を
   マージ先集合にマージ */
while (i <= mid) {
    work[k] = data[i];
    i++;
    k++;
}
while (j <= right) {
    work[k] = data[j];
    j++;
    k++;
}

またマージソートでは作業用のメモリが必要になりますので、そのメモリを引数の配列 work として関数に渡しています。

そしてこの配列 work にマージ結果を一旦格納し、最後に data にそのマージ結果をコピーしています。

/* マージ先集合をdataにコピー */
memcpy(&data[left], work, sizeof(int) * size);

スポンサーリンク

まとめ

このページではマージソートについて解説し、C言語で実装したプログラムの紹介を行いました。

マージソートはデータの集合に対して下記の３つを行うことで実現することができます。

• 集合を中央で２つに分割する
• 分割後の各集合のデータをそれぞれソートする
• ソート済みの各集合の小さいデータから順に新しい集合にコピーしてマージする

ポイントは分割後の各集合のデータのソートで、ここにもマージソートを適用することで再帰呼び出しで簡潔にプログラミングすることができます。

マージソートはプログラミングの授業や試験にもよく出題されるアルゴリズムですので、是非このページを参考ににてマスターしておきましょう！

本サイトでは、挿入ソート以外にも下記のソートについても解説しています。

• クイックソート
• 選択ソート
• 挿入ソート

下記リンク先でそれぞれについて解説していますので、他のソートアルゴリズムにも興味のある方は是非こちらも読んでみてください！

クイックソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

選択ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）

挿入ソートを図を使って分かりやすく解説（C言語サンプルプログラム付き）