26.1.6.27 併合整列

併合整列(マージソート)にもいろいろな形式のものがありますが，ここでは説明をわかりやすくするために，再帰的メソッドを使用します．

再帰的メソッドとは，あるメソッドの本体の中で直接に，あるいは他のメソッドを経由して間接に，自分自身を呼び出しているメソッドでした．自分の実行内容を記述するのに自分自身を使うのは変な気もしますが，きちんと書けばちゃんとした内容になります． 簡単な例を見てみましょう．これは階乗(1×2×3×…×n)を繰返し使わずに計算する例です．

static int fac(int x){
      if(x <= 1) return 1;
      else return x*fac(x-1);
  }

このメソッドをfac(4)と呼ぶと，

4 >1 なので 4*fac(3)が呼ばれ，fac(3)は，
3 >1 なので 3*fac(2)が呼ばれ，fac(2)は，
2 >1 なので 2*fac(1)が呼ばれ，fac(1)は，
1 <=1 なので"1"が結果となり，
2*1=2 がfac(2)の結果となり，
3*2*1=6 がfac(3)の結果となり
4*3*2*1=24 がfac(4)の結果となる，

というぐあいに計算が進行します．

この再帰的メソッドを使った併合整列の概略は以下のとおりです．

• 配列aと，整列すべき範囲top，tailを与えられる．

• top=tailなら，やることはない．

• tail-top >=1の場合

• 範囲をa[top]〜a[mid]とa[mid+1]〜a[tail]に，ほぼ等分に分割する．

• それぞれを(ふつうは自分自身を使用して)整列する．

• 作業領域w[top]〜w[tail]を準備する．

• a[top〜]とa[mid+1〜]の先頭から，小さい方をwへ書きうつす．

• w[top]〜w[tail]をa[top]〜a[tail]へ書き戻す．