归并排序

前言

归并的意思就是将两个或者两个以上的有序数组合成一个有序表。而归并排序就是将含有n个记录的子序列，每个子序列长度为1，然后两两归并，得到[n/2]个长度为2或者1的有序子序列，在两两归并，。。。。，如此重复，直到得到一个长度为n的有序序列为止

不妨先看代码，在从计算机角度去看看是如何执行代码过程的

void MergeSort(SqList *L){
  MSort(L->r,L->r,1,L->length);
}
//将SR[s..t]归并到TR1[s..t]
void MSort(int SR[],int TR1[],int s,int t){
  int m;
  int TR2[MAXSIZE+1];
  if(s==t)
    TR1[s]=SR[s];
  else
  {
    m=(s+t)/2;
    MSort(SR,TR2,s,m);
    MSort(SR,TR2,m+1,t);
    Merge(TR2,TR1,s,m,t);//将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
  }
}

里面有个递归 Merge(TR2,TR1,s,m,t);暂时先不管它，假设模拟的数组为{50,10,90,30,70,40,80,60,20}，所以知道初始化时SR和TR1都是该数组，s=1，t-9；由于s！=t，所以执行else中的语句。此时m=5，也就是正中间下标，所以开始先执行递归MSort(SR,TR2,1,5)，递归过程如下所示

其核心部分就是最后都变成叶子结点，递归结束，然后执行if里语句，不过此时TR1[s]=SR[s]，注意这里s是元素下标，所以第一次TR2={50,10}，然后就要执行Merge(TR2,TR1,s,m,t);前面是50与10已结归并了，暂时我们知道它就是把无需归并为有序就行了，即TR2={10,50}后面在详细分析它，
接下来同理，依次向上归并，最后得到{10,30,50,70,90}，同理，根结点右子树也一样，最终完成了归并

再来看看Merge(TR2,TR1,s,m,t)函数

void Merge(int SR[],int TR[],int i,int m,int n)
{
  int j,k,l;
   for(j=m+1,k=i;i<=m&&j<=n;k++)
   {
    if(SR[i]<SR[j])
      TR[k]=SR[i++];
    else
      TR[k]=SR[j++];
   }
   if(i<=m){  //将剩余元素归并
    for(l=0;l<=m-1;l++)
      TR[k+1]=SR[i+1];
  }
 if(j<=n)
 {
  for(l=0;l<n-j;l++)
    TR[k+1]=SR[j+1];
 }
}

就拿{10,30,50,70,90}和{20,40,60,80}归并为有序序列来说，此时i=1，m=5,n=9；进入for循环，此时j从6到9，i由1到5，k由1开始每次加1，并且k就是TR数组的下标，然后开始归并，左右子树的SR[i]=SR[1]=10与SR[j]=SR[6]=20开始比较，将较小数放入到一个初始化时空的TR[]中，比如是10，然后i++；否则j++，这样就可以得到有序序列了，但是最终当j=10时退出循环，而后面还有一些元素未归并，将执行后面if语句，将最后的90复制到最后，最终完成了归并

最后再来看看归并排序的时间复杂度，由于其与完全二叉树有关，最终得到其为O（nlogn)，而它也是比较占用内存但是很稳定的一种算法