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