MergeSort.java



/** ソートのアルゴリズム(その4 マージソート) */
public class MergeSort {

  /** 確認用のサンプルデータ */
    private static int[] test
                          = { 10, 75, 24, 32, 98,
                              72, 88, 43, 60, 35,
                              54, 62,  2, 12, 82,
                            };

  /** 作業領域用データ */
    private static int[] tmp = null;

  /** 処理の開始のメソッド(確認用) */
    public static void main( String[] argv ) {

   //ソートの作業
        sort( test, 0, test.length-1 );

   //ソートの結果の確認
        for( int i=0; i<test.length; i++ ) {
            System.out.println( (i+1) + ":" + test[i] );
        }
    }

  /** 与えられた範囲の値を2グループに分け、
      自分自身の仕事を再帰的に呼び出す */
    public static void sort( int[] array, int min, int max ) {

   //数が少ない時はバブルソートで処理する
        if( ( max - min ) < 5 ) {
            bsort( array, min, max ); 
            return;
        }

   //作業領域の確保(最初の呼び出しの時のみ)
        if( tmp == null )
            tmp = new int[ array.length ];

   //グループを2等分し、
   //それぞれのグループに対して同じことを繰り返す
        int size = max - min + 1;
        int half = size/2 + size%2;
        sort( array, min, min+half-1 );
        sort( array, min+half, max );

   //作業領域に大きい順にマージする
        int counter1 = 0;
        int counter2 = 0;
        for( int i=min; i<=max; i++ ) {
            if( counter1 > (half-1) ) {
               tmp[i] = array[ min+half+counter2 ];
               counter2++;
            }
            else if( counter2 > (max-min-half) ) {
               tmp[i] = array[ min+counter1 ];
               counter1++;
            }
            else if( array[ min+counter1 ] > array[ min+half+counter2 ] ) {
               tmp[i] = array[ min+counter1 ];
               counter1++;
            }
            else {
               tmp[i] = array[ min+half+counter2 ];
               counter2++;
            }
        }

   //作業領域の結果をコピーする
        for( int i=min; i<=max; i++ ) {
           array[i] = tmp[i];
        }
    }

  /** バブルソートで並び変えるメソッド */
    private static void bsort( int[] array, int min, int max ) {

        for( int i=min; i<max; i++ ) {
           for( int j=min; j<max-(i-min); j++ ) {
              if( array[j] < array[j+1] ) {
                  int tmp = array[j];
                  array[j] = array[j+1];
                  array[j+1] = tmp;
              }
           }
        }
    }
}