/**
  *归并排序思路：分治法思想  O(nlogn)
  *        把数组一分为二，二分为四
  *         四和为二，二和为一
  *
  */

 /**
  * 归并排序主方法
  *@params   待排序的数组
  *@params   初始位置
  *@params   最终位置
  */

 public  class  MergeSort
 {
     public  static  void   mergeSort(int[] resouceArr, int  begin  ,  int  end )
     {
         if  ( begin  <   end  )
         {
             int  middle  = ( begin + end ) / 2 ;
             mergeSort( resouceArr ,  begin  ,  middle );
             mergeSort( resouceArr ,  middle + 1 , end );
             _merge( resouceArr , begin , middle , end );
         }
     }
     /**
      *合并两个已经排好序数组的方法
      *由mergeSort()调用，定义为private,命名以下划线开头
      */
     private  static  void  _merge(int[] arr  ,  int  begin  ,  int  middle  ,  int  end  )
     {
         //获得左数组大小，右数组大小
         int  leftArrLength  =  middle -  begin  +  1 ;
         int  rightArrLength =  end  -  middle  ;
         //申请空间
         int[] leftArr = new int[leftArrLength + 1];
         int[] rightArr = new int[rightArrLength + 1];
         //初始化数组的值（把原数组的值一个一个复制quickArr到新数组中）
         for( int i = 0  ; i  <  leftArrLength  ;  i++)
         {
             leftArr[i] = arr[begin + i] ;
         }
         for( int j = 0  ; j  <  rightArrLength ;  j++)
         {
             rightArr[j] = arr[middle + j + 1] ;
         }
         //哨兵，放在最后
         leftArr[leftArrLength] = 65536 ;
         rightArr[rightArrLength] = 65536 ;

         int  i  =  0  ;
         int  j  =  0  ;
         for(int k = begin ; k <= end  ;  k++ )
         {
             if( leftArr[i] <= rightArr[j] )
             {
                 arr[k] = leftArr[i] ;
                 i = i + 1 ;
             }
             else
             {
                 arr[k] = rightArr[j];
                 j = j + 1 ;
             }
         }
     }
 }