マージソート

あらかじめ整列してある2つの配列を合体させて、新しい、整列された配列を得るのは容易です。マージソートはこれに着目して、並べ替えたい配列を再帰的に分割していき、再び併合(マージ)していくことで、並び替えを実現しようとする、ソートアルゴリズムです。

考え方

次の図は、マージソートが行われる過程を表しています。

merge-sort-image.gif (8666 バイト)

ばらばらな順番で与えられた配列データは、まず始めに小さい配列へと分解されます。このとき、マージソートでは各配列がほぼ2分割されるように分解していきます。

もっとも小さい配列(要素数1)まで分解されたら、それを順序良く併合していきます。このとき、2つの配列の先頭から小さい方を取り出して新しい配列を作成するようにすれば、取り出すだけで整列された配列を作成することができます。

アルゴリズム

Java で書いたマージソートアルゴリズムを以下に示します。

  /*
   * マージ
   * 2つの配列a1[]とa2[]を併合してa[]を作ります。
   */
  void merge(int[] a1,int[] a2,int[] a){
    int i=0,j=0;
    while(i<a1.length || j<a2.length){
      if(j>=a2.length || (i<a1.length && a1[i]<a2[j])){
	a[i+j]=a1[i];
	i++;
      }
      else{
	a[i+j]=a2[j];
	j++;
      }
    }
  }

  /*
   * マージソート
   * 既にソート済みの2つの配列を併合して新しい配列を
   * 生成することで、データのソートを行います。
   */
  void mergeSort(int[] a){
    if(a.length>1){
      int m=a.length/2;
      int n=a.length-m;
      int[] a1=new int[m];
      int[] a2=new int[n];
      for(int i=0;i<m;i++) a1[i]=a[i];
      for(int i=0;i<n;i++) a2[i]=a[m+i];
      mergeSort(a1);
      mergeSort(a2);
      merge(a1,a2,a);
    }
  }

  /*
   * ソート
   */
  public void sort(int[] a){
    mergeSort(a);
  }
【アルゴリズム5】 マージソート

メソッド mergeSort() は、与えられた配列 a[ ] をほぼ2等分し、それぞれの配列を mergeSort() で並べ替えた後、2つを併合して1つの配列にしています。この処理は、配列の大きさが1になるまで、再帰的に呼び出されます。

メソッド merge() は、3つの配列 a1[ ] , a2[ ] , a[ ] を受けて、a1 と a2 を併合した配列を a に格納して戻ります。このとき、a1 , a2 の小さいほうから順番に取り出して a に格納するので、a1 と a2 が整列された配列ならば、a も整列された配列になります。

マージソートの動作

マージソートを可視化して行うアプレットを、下に示します。

このアプレットを見ると、上から徐々に、並べ替えられた部分が広がっていくことがわかります。まず全体の 1/8 が整列し、続いて 1/4 、1/2 が整列して、最後に全体が並べ変わる、といった具合です。途中で止めながらチェックすると、分かりやすいと思います。

計算時間の評価

m 個の配列と n 個の配列とを併合するには m+n に比例した時間がかかります。また、N 個のデータを1個ずつになるまで2分割していくには log(N) 時間かかります。

したがって、データ数が N の場合、分解に要する時間が N log(N)、併合に要する時間も N log(N) となりますから、合計 2 N log(N) の時間がかかることになり、オーダーは O(N log(N)) となります。

← prev | next →