排序——归并排序

基本思想：

    首先，将R[1]~R[n]看成n个长度为1的有序表，将相邻的有序表成对归并，得到n/2个长度为2的有序表；然后，再将这些有序表成对归并，得到n/4个长度为4的有序表，如此反复进行下去，得到一个长度为n的有序表。

    （与前面介绍的几种排序方法不同，归并排序需要用到一个和R同类型的辅助数组S）

算法关键步骤：

    1、定义两组归并算法

        merge(list R,list S,int a,int b,int c),

     它将有序表R[a]~R[b]和R[b+1]~R[c]归并到S[a]~S[c]中

     2、定义一趟归并算法

        mergepass(list R,list S,int &m)

     它将R中的有序表成对归并到S中。m是归并前R中第一个有序表的长度，一趟归并后m的值*2

     令m的初始值为1，在m<n的情况下，交替调用一趟归并算法mergepass(R,S,m)和mergepass(S,R,m)

代码：

//两组归并
void merge(list R,list S,int a,int b,int c)
{
  int i,j,k;
  i=a; j=b+1; k=a;
  while((i<=b)&&(j<=c)) 
    if(R[i].key<=R[j].key)
         S[k++]=R[i++];                   
    else S[k++]=R[j++];                           
  while(i<=b) S[k++]=R[i++];                  
  while(j<=c) S[k++]=R[j++]
} 
//一趟归并          
void mergepass(list R,list S,int &m)         
{                               
  int i=1,j;                     
  while(i+2*m-1<=n){  //相邻的两个有序表长度都是m
    merge(R,S,i,i+m-1,i+2*m-1);   
    i=i+2*m;                      
  }                              
  if(i+m-1<n)//剩下两个有序表，最后一个有序表长度小于m       
     merge(R,S,i,i+m-1,n);         
  else       //剩下一个有序表                         
     for(j=i;j<=n;j++) S[j]=R[j];                   
  m=2*m;                         
}
//归并排序
void mergesort()         
{                        
  list S;
  int m=1;
  while(m<n) {
    mergepass(R,S,m);
    mergepass(S,R,m);
  }
}
           

算法分析：

    对n个元素进行归并排序，需要经过log2n趟

归并，每一趟归并，其排序码比较次数不超过n–1，

元素移动次数都是n。

    因此，归并排序的执行时间是O(nlog2n)。

    归并排序是稳定的排序。