26.1.6.28 再帰的併合整列

併合整列のプログラムです．

class SortM{
    static int n=10;
    static int a[ ]=new int[n];
    public static void main(String argv[ ]){
	Alib.prepare(a);           // 値を乱数で準備
	Alib.show(a);
	Alib.ln();
	sortm(0, a.length-1);      // 整列
	Alib.show(a);
	Alib.ln();
    }

    static void sortm(int top, int tail){
	if(tail > top){
	    int w[ ]=new int[tail-top+1];
	    int iw, i1, i2, mid=(top+tail)/2;
	    sortm(top, mid);          // 前半分を整列
	    sortm(mid+1, tail);       // 後半分を整列
	    i1=top; i2=mid+1; iw=0;
	    while(i1<=mid && i2<=tail)  // 両方とも残っている場合
		if(a[i1] < a[i2]){
		    w[iw]=a[i1]; iw=iw+1; i1=i1+1;
		}else{
		    w[iw]=a[i2]; iw=iw+1; i2=i2+1;
		}
	    while(i1<=mid){               // 前半の残り
		w[iw]=a[i1]; iw=iw+1; i1=i1+1;
	    }           
	    while(i2<=tail){              // 後半の残り
		w[iw]=a[i2]; iw=iw+1; i2=i2+1;
	    }
	    for(int i=top; i <= tail; i=i+1)   // 書き戻し
		a[i]=w[i-top];
	}
    }   
}

SortM.java (iso-2022-jp)