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

マージソート解説ページのアイキャッチ

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

マージソートとは

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

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

クイックソート解説ページのアイキャッチクイックソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

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

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

マージソートの考え方

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

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

上記は昇順にソートする場合の考え方になります

降順にソートする場合は「小さい」を「大きい」に読み替えてください

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

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

データ全体を2分割する様子

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

各集合それぞれをソートする様子

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

2つの集合のデータの小さいものから順にマージしていく様子

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

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

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

スポンサーリンク

集合のマージ

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

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

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

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

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

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

マージを行う2つの集合

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

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

1番小さいデータの候補

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

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

2つの先頭のデータの小さい方をマージする様子1

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

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

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

2番目に小さいデータの候補

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

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

2つの先頭のデータの小さい方をマージする様子2

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

2つの先頭のデータの小さい方をマージする様子3

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

2つの先頭のデータの小さい方をマージする様子4

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

2つの先頭のデータの小さい方をマージする様子ラスト

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

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

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

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

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

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

メモリ量

マージ時にはマージ先となる新たな集合が必要になります

この集合の分、メモリ量が余分に必要になります

クイックソート等のように集合内のデータのみの交換ではソートが行えませんので、これらに比較して必要メモリ量が増加します

分割した集合のソート

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

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

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

マージソートです!

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

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

分割した集合

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

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

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

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

集合の分割

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

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

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

集合の分割

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

集合内のデータの並び

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

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

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

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

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

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

集合のマージ

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

集合のマージ

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

分割後の集合のソート結果

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

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

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

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

mergesort.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");
}

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

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

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

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

    /* 2つの集合のどちらかが全てマージ済みになるまでループ */
    while (i <= mid && j <= right) {
        /* マージ済みデータを抜いた2つの集合の
           先頭のデータの小さい方をマージ */
        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;


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

    /* 集合を中央で2つに分割する */
    /* 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 関数で主に行っているのはマージソートとはで紹介した下記の3つです。

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

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

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

mergSort関数の再起呼び出し
/* 分割後の各集合のデータをそれぞれソートする */
mergeSort(data, left, mid, work);
mergeSort(data, mid + 1, right, work);

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

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

merge 関数

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

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

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

マージの前半処理
/* 2つの集合のどちらかが全てマージ済みになるまでループ */
while (i <= mid && j <= right) {
    /* マージ済みデータを抜いた2つの集合の
       先頭のデータの小さい方をマージ */
    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言語で実装したプログラムの紹介を行いました。

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

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

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

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

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

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

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

クイックソート解説ページのアイキャッチクイックソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) 選択ソート解説ページのアイキャッチ選択ソートを図を使って分かりやすく解説(C言語サンプルプログラム付き) 挿入ソートの解説ページアイキャッチ挿入ソートを図を使って分かりやすく解説(C言語サンプルプログラム付き)

2 COMMENTS

Kちゃん

自分で書いたときにうまく行かなかったのは、「マージ済みでないデータが残っている集合をマージ先集合にマージ」の理解が出来ていないことが原因だったのがわかりました。
ありがとうございます。

返信する
daeu

Kちゃん

コメントありがとうございます。
そして、このページのリクエストありがとうございました!

問題が解決できたのであれば、記事を書いた自分としてはこんなに嬉しいことはないです。
役に立ってよかったです。

また何かリクエストあれば気軽に言ってください!

返信する

daeu へ返信する コメントをキャンセル

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です