マージソート | Programming Place Plus アルゴリズムとデータ構造編【整列アルゴリズム】 第7章

アルゴリズムとデータ構造編【整列】 第7章 マージソート

先頭へ戻る

この章の概要

この章の概要です。


マージソート

この章では、マージソート(併合ソート)を取り上げます。

名前に「マージ」が含まれているように、このソートアルゴリズムは、マージ処理を利用します。マージについては、【その他】第4章で説明しているので、そちらを参照して下さい。

前章のクイックソートと同様に、マージソートも再帰の考え方が重要になります。

まず、元のデータ列(これは1つ)を、1要素ずつのばらばらな状態になるまで分割します。そして、2つのデータ列をマージすることを繰り返していき、1つのデータ列を完成させます。マージの際に、昇順(あるいは降順)になるようにうまく操作すれば、マージ結果をソート済みな状態にできます。

具体的な流れを説明します。元のデータ列は、{7, 2, 6, 4, 3, 8, 1, 5} とします。

まず、データ列を2つに分割します。これは単純に、真ん中から2つに分ければいいだけです。結果、

{7, 2, 6, 4}  {3, 8, 1, 5}

このように分かれます。分割前のデータ数が奇数だと綺麗に分かれませんが、特に気にする必要はありません。これを再帰的に繰り返します。まず左側だけ見ていきます。

{7, 2} {6, 4}  {3, 8, 1, 5}
{7} {2} {6, 4}  {3, 8, 1, 5}

要素数が1つになったら、その部分に対する再帰処理を終えて、マージ作業を行います。上の状態でいえば、{7} {2} の部分をマージします。

{2, 7} {6, 4}  {3, 8, 1, 5}

このように繰り返していくと、元の配列の左半分がソート済みになります。

{2, 4, 6, 7}  {3, 8, 1, 5}

まったく同じ過程を右半分にも行います。

{2, 4, 6, 7}  {3, 8} {1, 5}
{2, 4, 6, 7}  {3} {8} {1} {5}
{2, 4, 6, 7}  {3, 8} {1, 5}
{2, 4, 6, 7}  {1, 3, 5, 8}

最後の2つの塊もマージされると、

{1, 2, 3, 4, 5, 6, 7, 8}

となり、ソート作業が完了します。

肝心のマージのやり方については、【その他】第4章で取り上げている通りです。具体的には、2つのデータ列の先頭要素を比較して、小さい方(降順にソートする場合は大きい方)を取り出して、結果を受け取る配列へ格納します。データ列が空になったら、他方のデータ列の残りの要素すべてを取り出して、結果の配列へ移します。

配列に対するマージソート

では、実際にマージソートを行うプログラムを確認しましょう。ここでは、配列をマージソートでソートしてみます。

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

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void merge_sort(int* array, size_t size);
static void merge_sort_rec(int* array, int begin, int end, int* work);
static void merge(int* array, int begin, int end, int mid, int* work);
static void print_array(const int* array, size_t size);

int main(void)
{
    int array[] = {7, 2, 9, 6, 4, 3, 8, 1, 5};

    print_array( array, SIZE_OF_ARRAY(array) );
    merge_sort( array, SIZE_OF_ARRAY(array) );
    print_array( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    マージソート (昇順)
*/
void merge_sort(int* array, size_t size)
{
    int* work;

    /* 作業用領域を確保 */
    work = malloc( sizeof(int) * size );

    /* 配列全体を対象にする */
    merge_sort_rec( array, 0, size - 1, work );

    free( work );
}

/*
    マージソート (再帰部分、昇順)
*/
void merge_sort_rec(int* array, int begin, int end, int* work)
{
    int mid;

    /* 要素が1つしかなければ終了 */
    if( begin >= end ){
        return;
    }


    /* 2つのデータ列に分割して、それぞれを再帰的に処理 */
    mid = (begin + end) / 2;
    merge_sort_rec( array, begin, mid, work );
    merge_sort_rec( array, mid + 1, end, work );

    /* マージ */
    merge( array, begin, end, mid, work );
}

/*
    マージ
*/
void merge(int* array, int begin, int end, int mid, int* work)
{
    int i, j, k;

    /* 前半の要素を作業用配列へ */
    for( i = begin; i <= mid; ++i){
        work[i] = array[i];
    }

    /* 後半の要素を逆順に作業用配列へ */
    for( i = mid + 1, j = end; i <= end; ++i, --j){
        work[i] = array[j];
    }

    /* 作業用配列の両端から取り出した要素をマージ */
    i = begin;
    j = end;
    for( k = begin; k <= end; ++k) {
        /* 昇順にソートするので、小さい方の要素を結果の配列へ移す。 */
        if( work[i] <= work[j] ){ /* == の場合は先頭を優先すると安定なソートになる */
            array[k] = work[i];
            ++i;
        }
        else{
            array[k] = work[j];
            --j;
        }
    }
}

/*
    配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
    size_t i;

    for( i = 0; i < size; ++i ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
}

実行結果:

7 2 9 6 4 3 8 1 5
1 2 3 4 5 6 7 8 9

merge_sort関数が入口になっています。ここでまず、作業用領域を確保しています。作業用領域は、ソート対象の配列の要素数以上が必要になります。どんな大きさの配列が対象となるか分からないので、動的に確保するようにしています。

作業用領域が必要になる理由は、マージする2つのデータ列と、マージ結果を格納する配列がそれぞれ必要となるためです。元の配列=結果を格納する配列になりますから、マージ前の2つのデータ列を置く場所を作らないと、マージ作業中に、結果を格納する配列が破壊されてしまいます。

次に merge_sort_rec関数です。まず、対象の範囲に含まれている要素数を調べ、要素が2つ以上存在しないのなら何もせずに終了しています。次に、対象の範囲を2つに分割し、それぞれの範囲を対象として merge_sort_rec関数を再帰呼び出しします。

その後、merge関数が呼び出されて、マージ処理が行われます。まず、2つの範囲を作業用配列へコピーしています。このとき、前半部分は作業用配列の前半へそのまま素直にコピーしますが、後半部分は逆順になるようにコピーします。

このようにすることで、前半部分のうちの最小の値を持った要素が作業用配列の先頭に来て、後半部分のうちの最小の値を持った要素が作業用配列の末尾に来ます。従って、マージの過程では、作業用配列の先頭と末尾の要素を調べ、小さい方(降順にソートするなら大きい方)を元の配列へ格納するようにすれば良いということになります。(マージのアルゴリズムについては、【その他】第4章を確認して下さい)。

ここではマージ処理を1つの関数にまとめましたが、関数呼び出しのコストが馬鹿にならないようならば、merge_sort_rec関数内に展開してしまった方がいいでしょう。

連結リストに対するマージソート

前の項では、配列を使ってマージソートの実装を確認しました。しかし、実はマージソートは、配列のソートにはあまり向いていません。なぜなら、大きな作業用配列を用意しなければならないという欠点があるからです。

一方で、マージソートは連結リスト(【データ構造】第3章参照)のソートに適しています。連結リストの場合、作業用の領域が必要なく、ポインタの付け替えだけで済むからです。

配列版のサンプルプログラムを、連結リストに置き換えると、次のようになります。連結リストの実装には、コードライブラリの ppps_int_slist を使用しています。

#include <stdio.h>
#include "ppps_int_slist.h"

static void merge_sort(PPPSIntSlist list);
static PPPSIntSlist merge_sort_rec(PPPSIntSlist list);
static PPPSIntSlist merge(PPPSIntSlist a, PPPSIntSlist b);

int main(void)
{
    PPPSIntSlist list = ppps_int_slist_create();

    ppps_int_slist_add_tail( list, 7 );
    ppps_int_slist_add_tail( list, 2 );
    ppps_int_slist_add_tail( list, 9 );
    ppps_int_slist_add_tail( list, 6 );
    ppps_int_slist_add_tail( list, 4 );
    ppps_int_slist_add_tail( list, 3 );
    ppps_int_slist_add_tail( list, 8 );
    ppps_int_slist_add_tail( list, 1 );
    ppps_int_slist_add_tail( list, 5 );


    puts( "ソート前" );
    ppps_int_slist_print( list );

    merge_sort( list );

    puts( "ソート後" );
    ppps_int_slist_print( list );


    ppps_int_slist_delete( list );

    return 0;
}

/*
    マージソート (昇順)
*/
void merge_sort(PPPSIntSlist list)
{
    PPPSIntSlist result;

    if( list == NULL ){
        return;
    }

    /* リスト全体を対象にする */
    result = merge_sort_rec( list->next );

    list->next = result;
}

/*
    マージソート (再帰部分、昇順)
*/
PPPSIntSlist merge_sort_rec(PPPSIntSlist list)
{
    PPPSIntSlist a;
    PPPSIntSlist b;
    PPPSIntSlist x;


    /* 要素が1つしかなければ終了 */
    if( list == NULL || list->next == NULL ){
        return list;
    }


    /* 2つのリストに分割するため、リストの中心を探す */
    a = list;
    b = list->next;
    if( b != NULL ){
        b = b->next;
    }

    while( b != NULL ){
        a = a->next;
        b = b->next;
        if( b != NULL ){
            b = b->next;
        }
    }


    /* リストを前半と後半に分離 */
    x = a->next;
    a->next = NULL;


    /* 前半と後半のリストをマージする */
    return merge( merge_sort_rec(list), merge_sort_rec(x) );
}

/*
    マージ
*/
PPPSIntSlist merge(PPPSIntSlist a, PPPSIntSlist b)
{
    struct PPPSIntSlist_tag result;
    PPPSIntSlist x = &result;

    /* リストをマージ */
    while( a != NULL && b != NULL ){
        /* 昇順にソートするので、小さい方の要素を結果を優先する */
        if( a->value <= b->value ){ /* == の場合は先頭を優先すると安定なソートになる */
            x->next = a;
            x = x->next;
            a = a->next;
        }
        else{
            x->next = b;
            x = x->next;
            b = b->next;
        }
    }

    /* 残っている要素を、末尾へ連結 */
    if( a == NULL ){
        x->next = b;
    }
    else{
        x->next = a;
    }

    return result.next;
}

実行結果:

ソート前
7
2
9
6
4
3
8
1
5
ソート後
1
2
3
4
5
6
7
8
9

配列版と異なり、merge_sort関数内で作業用の領域を確保するようなことはしていません。

merge_sort_rec関数でしていることは、基本的に配列版と同じです。対象のデータ列を分割する際、連結リストの中心で分けるようにしています。単方向線形リストで、中心の要素を探すためには、先頭を指すポインタを2つ用意し、一方は1つずつ、他方は2つずつ先へ先へと進めていきます。こうすれば、2つずつ進めている方が末尾に行き着いたとき、1つずつ進めていた方のポインタがちょうど中心の要素を指していることになります

merge関数も、連結リストの操作に慣れていないと、かなり複雑で難しく見えると思いますが、していることは配列版と同じです。


ボトムアップ方式のマージソート

ここまでに取り上げたマージソートの実装は、トップダウン方式と呼ばれることがあります。これは、分割を繰り返して、要素を1つ1つのばらばらな状態にしていく過程が、木構造(【データ構造】第7章)を上から下へ降りていくように見えることに由来します。

一方で、ボトムアップ方式と呼ばれる実装も存在します。こちらは、ソート前のデータ列が、既に1要素ずつに分割済みであるように仮定して、うまく結合していくことを考える方式です。分割済みな状態から開始して、ソート済みのデータ列を作り上げていく過程を、木構造を下から上へ上がっていくように見立てて、ボトムアップ方式と呼びます。

それでは、ボトムアップ方式での動作を詳しく見ていきます。まず、ソート前のデータ列の要素を、それぞれ長さ1の列とみなします。元のデータ列を、{7, 2, 6, 4, 3, 8, 1, 5} とすると、

{7} {2} {6} {4} {3} {8} {1} {5}

のように考えるということです。このとき、それぞれの塊は、要素が1つしか無いので、ソート済みであると考えることができます。

次に、隣り合う要素同士2つずつでマージしていきます。このとき、昇順(あるいは降順)になるようにマージします。すると、次のようになります。

{2, 7} {4, 6} {3, 8} {1, 5}

同じことを繰り返します。

{2, 4, 6, 7} {1, 3, 5, 8}
{1, 2, 3, 4, 5, 6, 7, 8}

これでソート完了となります。

木構造に見立てたとき、どこまで下へ降りていくことになるのか事前に分からないトップダウン方式と違い、ボトムアップ方式の場合は、隣の要素とのマージを繰り返すだけなので、再帰処理ではなく、単純なループ構造で実現できる点が特徴です。つまり、クイックソート(前章参照)と同様、再帰による実装(トップダウン方式)と、非再帰による実装(ボトムアップ方式)とが存在する訳です。

それでは、ボトムアップ方式でのマージソートの実装を見てみましょう。

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

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define MIN(a, b)  (a < b) ? (a) : (b)

static void merge_sort(int* array, size_t size);
static void merge_sort_bottomup(int* array, int begin, int end, int* work);
static void merge(int* array, int begin, int end, int mid, int* work);
static void print_array(const int* array, size_t size);

int main(void)
{
    int array[] = {7, 2, 9, 6, 4, 3, 8, 1, 5};

    print_array( array, SIZE_OF_ARRAY(array) );
    merge_sort( array, SIZE_OF_ARRAY(array) );
    print_array( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    マージソート (昇順)
*/
void merge_sort(int* array, size_t size)
{
    int* work;

    /* 作業用領域を確保 */
    work = malloc( sizeof(int) * size );

    /* 配列全体を対象にする */
    merge_sort_bottomup( array, 0, size - 1, work );

    free( work );
}

/*
    マージソート (昇順)
*/
void merge_sort_bottomup(int* array, int begin, int end, int* work)
{
    int i, j;

    for( i = 1; i <= end - begin; i *= 2 ){
        for( j = begin; j <= end - i; j += i * 2 ){
            merge( array, j, MIN(j + i * 2 - 1, end), j + i - 1, work);
        }
    }
}

/*
    マージ
*/
void merge(int* array, int begin, int end, int mid, int* work)
{
    int i, j, k;

    /* 前半の要素を作業用配列へ */
    for( i = begin; i <= mid; ++i){
        work[i] = array[i];
    }

    /* 後半の要素を逆順に作業用配列へ */
    for( i = mid + 1, j = end; i <= end; ++i, --j){
        work[i] = array[j];
    }

    /* 作業用配列の両端から取り出した要素をマージ */
    i = begin;
    j = end;
    for( k = begin; k <= end; ++k) {
        /* 昇順にソートするので、小さい方の要素を結果の配列へ移す。 */
        if( work[i] <= work[j] ){ /* == の場合は先頭を優先すると安定なソートになる */
            array[k] = work[i];
            ++i;
        }
        else{
            array[k] = work[j];
            --j;
        }
    }
}

/*
    配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
    size_t i;

    for( i = 0; i < size; ++i ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
}

実行結果:

7 2 9 6 4 3 8 1 5
1 2 3 4 5 6 7 8 9

merge_sort_bottomup関数以外は、再帰版と同じです。

merge_sort_bottomup関数は、空白行を入れてもわずか 7行で、再帰もしていないので、非常にすっきりして見えますが、ぱっと見では分かりづらい処理になっています。

まず、外側の for文では、マージ範囲の大きさを表す変数を制御しています。最初は i = 1 で始まり、1周ごとに 2倍されていきます。つまり、最初は 1個の要素と、その隣の 1個の要素とをマージします。次回は、2個の要素と、その隣の 2個の要素とをマージしようとします。

内側の for文では、マージ範囲の左端の位置を制御しています。最初は必ず begin から始まっていますが、これはソート対象範囲の先頭の位置です。1周ごとに、変数i の 2倍だけ増加します。変数i がマージ範囲の大きさですから、次の範囲の先頭まで進めているということです。

2つの for文の中では、merge関数を呼び出してマージ処理を実行しています。終端位置の指定で、MINマクロを使って少し複雑なことをしていますが、これはソート範囲の終端を超えてしまわないようにするための処置です。変数i を、配列の大きさを気にせずに増加させているので、MINマクロによる制御を加えないと範囲外アクセスが起こる可能性があります。

性能

ここでは、マージソートとクイックソートの性能を比較してみます。それぞれの再帰版、非再帰版で実験しましょう。ここでは、それぞれのアルゴリズムは、コードライブラリの ppps_int_sort を使うようにしています。実装は解説通りのものになっていると考えて頂いて結構です。

#include <stdio.h>
#include <stdlib.h>
#include "ppp_perform.h"
#include "ppps_int_sort.h"

#define ARRAY_SIZE              100000
#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

static void init_array(int* array, size_t size);

int main(void)
{
    int array[ARRAY_SIZE];


    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    ppps_merge_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("merge_sort");

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    ppps_merge_sort_no_recursive( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("merge_sort_no_recursive");

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    ppps_quick_sort( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("quick_sort");

    init_array( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_BEGIN(1);
    ppps_quick_sort_no_recursive( array, SIZE_OF_ARRAY(array) );
    PPP_CHECK_PERFORM_END("quick_sort_no_recursive");

    return 0;
}

/*
    配列を初期化
*/
void init_array(int* array, size_t size)
{
    size_t i;

    srand(0);

    for(i = 0; i < size; ++i){
        array[i] = rand() % size;
    }
}

実行結果:

merge_sort: 0.055000 seconds
merge_sort_no_recursive: 0.034000 seconds
quick_sort: 0.027000 seconds
quick_sort_no_recursive: 0.023000 seconds

実行結果を見ると、次のことが分かります。

計算量としては、マージソートは O(n log n) であり、これはクイックソートと同じです。しかし実際には、マージソートの方が処理が複雑になるため、クイックソートの性能には敵いません

一方で、クイックソートの場合、データの並び方によっては、計算量が O(n2) まで落ち込むのに対して、マージソートは常に O(n log n) の計算量が保証されます。これは、マージソートの場合、分割の際には要素の値の大小関係を見ていないため、データ列がどのように並んでいても無関係に処理できるからです。

まとめ

マージソートの計算量は、O(n log n) です。これはクイックソートと同じですが、実際の性能はクイックソートにはかないません。マージソートの方が、処理内容が複雑になるためです。

また、クイックソートが最悪時には計算量が O(n2) まで落ち込むのとは異なり、マージソートの計算量は安定して、O(n log n) です

このように、良い計算量が常に維持されることは利点と言えますが、前章で説明している通り、クイックソートの性能悪化は軽減する手段があるので、大抵はクイックソートを使う方が高速です。

ただ、マージソートは、クイックソートと違って、安定なソートアルゴリズムであるという利点もあります。ですから、安定性が不要ならクイックソートを使い、安定でなければならないときはマージソートを使うという選択基準もあり得ます。

他のアルゴリズムと違い、マージソートの性能を語る上では、メモリ使用量の性能にも触れておく必要があります。マージソートを使って配列をソートする場合、マージの作業用に O(n) に相当する領域を用意しなければなりません。ただし、連結リストをソートする場合は、作業用領域を必要としないので、これは当てはまりません。このような事情があるため、実のところ、マージソートは配列のソートにはあまり向いていません。

マージソートは、連結リストや、ディスク上のデータのソートを効率的に行えるという利点もあります。他のソートアルゴリズムでも出来なくはないですが、ほとんどの場合、非効率になってしまいます。


練習問題

問題① ボトムアップ方式のマージソートで、連結リストをソートするプログラムを作成して下さい。(これはそれほど簡単にはいきません。あるデータ構造を併用することがポイントです)

問題② マージソートの性能改善の手段として、ソート対象の要素数が十分小さくなったら、その部分のソートに挿入ソート(第4章)を使うという方法があります。この方法で、トップダウン方式の配列に対するマージソートを改造して、パフォーマンスを測定して下さい(前章の練習問題③では、クイックソートに対して、同じ方法による性能改善を取り上げています)。


解答ページはこちら

参考リンク



更新履歴

'2018/2/22 要素数を意味している「サイズ」について、「要素数」に表記を改めた。

'2017/5/23 「プログラム例」の項を、「配列に対するマージソート」に修正し、 これに合わせて、文章を修正。

'2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

'2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

'2015/1/17 余計な文章が混入していたので削除。
説明文とサンプルプログラムで使っている名前が一致していなかった箇所を修正。

'2013/6/1 配列版の merge関数で、前半要素をコピーする際の for文の条件式が間違っていたのを修正。

'2013/1/26 新規作成。



前の章へ(第6章 クイックソート)

次の章へ(第8章 ヒープソート)

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ


このエントリーをはてなブックマークに追加
rss1.0 取得ボタン RSS