ch8_9.txt

清华出版社出版

void mergesort(JD r[],int n)
{  int i,s=1;
   JD t[M];
   while(s<n)
   {  tgb(s,n,r,t);
      s*=2;
      if(s<n) { tgb(s,n,t,r); s*=2; }
      else  {  i=1;
               while(i<=n)  r[i]=t[i++];
            }
   }
}
/*趟归并，s为有序子表长度*/
void tgb(int s,int n,JD r[],JD t[])
{  int i=1;
   while(i<=(n-2*s+1))
   {  merge(r,i,i+s-1,i+2*s-1,t);
      i=i+2*s;
   }
   if(i<(n-s+1))  merge(r,i,i+s-1,n,t);
   else   
      while(i<=n)  t[i]=r[i++];
}
/* 合并首尾相接的两个有序子表（h,m)和(m+1,w)*/
void merge(JD r[],int h,int m,int w,JD t[])
{  int i,j,k;
   i=h; j=m+1; k=h-1;
   while((i<=m)&&(j<=w))
   {  k++;
      if(r[i].key<=r[j].key)
         t[k]=r[i++];
      else
         t[k]=r[j++];
   }
   if(i>m)
      while(j<=w)  t[++k]=r[j++];
   else
      while(i<=m)  t[++k]=r[i++];
}