//本程序取自王曉東編著“算法分析與設計”第 35 頁，例
//合并排序的遞歸解法
class mergeSort2_7_1
  {
   public static void mergeSort(int [] a,int left,int right)
    {
     int b[]=new int[a.length];
     if(left<right){//至少有2個元素
     int i=(left+right)/2;//取中點 
     mergeSort(a,left,i);
     mergeSort(a,i+1,right);
     merge(a,b,left,i,right);//合并到數組 b
     copy(a,b,left,right);//復制回數組 a
      }
     }
   public static void copy(int[] a,int[] b,int i,int j)
    {
      int k;
      for(k=i;k<=j;k++)
      a[k]=b[k];
     } 
  public static void merge(int [] c,int [] d,int l,int m,int r)
     {//合并c[l:m]和c[m+1:r]到d[l:m]
      int i=l,
          j=m+1,
          k=l;
      while((i<=m)&&(j<=r))
          if(c[i]-c[j]<=0)
             d[k++]=c[i++];
          else d[k++]=c[j++];
          if(i>m)
          for(int q=j;q<=r;q++)
              d[k++]=c[q];
          else 
           for(int q=i;q<=m;q++)
              d[k++]=c[q];
      }
   public static void main(String args[])
     {
      int i;
      int t[]={4,8,3,7,1,5,6,2};
      for(i=0;i<t.length;i++)
      System.out.print(t[i]+"  ");
      System.out.println();
      mergeSort(t,0,t.length-1);
       for(i=0;i<t.length;i++)
      System.out.print(t[i]+"  ");
      System.out.println();
     }
  }