//本程序取自王曉東編著“算法分析與設計”第 34頁，例
//合并排序的非遞歸解法
class mergeSort2_7
  {
   public static void mergeSort(int [] a)
    {
     int [] b=new int[a.length];
     int s=1;
     while(s<a.length){
        mergePass(a,b,s);//合并到數組 b
        s+=s;
        mergePass(b,a,s);//合并到數組 a
        s+=s;
        }
     }
   public static void mergePass(int [] x,int [] y,int s)
     {//合并大小為s的相鄰子數組 
      int i=0;
      while(i<=x.length-2*s)
      {//合并大小為s的相鄰2段子數組
      merge(x,y,i,i+s-1,i+2*s-1);
      i=i+2*s;
      }
      //剩下的元素個數少于2s
      if(i+s<x.length)
      merge(x,y,i,i+s-1,x.length-1);
      else
      //復制到y
      for(int j=i;j<x.length;j++)
       y[j]=x[j];
     }
  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);
       for(i=0;i<t.length;i++)
      System.out.print(t[i]+"  ");
      System.out.println();
     }
  }