6.3 归并排序Mergesort

归并排序应用数据分组的方法，将输入数据分成元素数量相同的多个分组，然后两两归并，组织成树形序，最后得到一个有序文件。归并排序早期用在内存有限时，存储器的数据只能部分调入内存，只能分组排序。归并排序是两个有序表的归并，再组成一个有序表。因此，归并排序实现了局部有序。

例题是清华大学版《数据结构》，10.5 归并排序。

源程序

   C语言伪代码

void Merge(RcdType SR[], RcdType TR[], int i, int m, int n){

        /*2路归并有序的SR[i..m]与SR[m+1..n]，实现有序的目标文件TR[i..n]*/

for(j=m+1,k=i;  i<=m&&j<=n;  ++k){

     if(LQ(SR[i].key,SR[j].key)  TR[k]=SR[i++];

         /*LQ(a,b)=(a<=b)*/

        /*SR[i]比SR[j]小，应存放到TR[k]中，i移动到下一元素*/

else

       TR[k]=SR[j++];

      /*否则，SR[j]比SR[i]小，应存放到TR[k]中，j移动到下一元素*/

    }

    if (i<=m)  TR[k..n]=SR[i..m];

 /*SR[m+1..n]全部比较完成，存放到TR[]中，因此SR[i..m]应顺序存放到TR[]*/

    if (j<=n)  TR