7.5.1 归并排序
归并的含义是将两个或两个以上的有序表组合成一个新的有序表。 假定待排序表中含有N个记录，则可以看成是N个有序的子表，每个子表长度为1，然后两两归并，得到[n/2]个长度为2或1的有序表; 在两两归并，。。。如此重复，直至合并成一个长度为N的有序表为止，这种排序方法称为2-路归并排序。 下面是2路归并排序的例子： 初始关键字：【49】，【38】，【65】，【97】，【76】，【13】，【27】 一趟归并后：【38,49】，【65,97】，【76,13】，【27】 二趟归并后：【38 49 65 97】，【13 27 76】 三趟归并后：【13 27 38 49 65 76 97】 Merge()的功能是将前后相邻的两个有序表归并为一个有序表的算法。 设两段有序表A[low...mid]、A[mid+1...+high]存放在同一顺序表中相邻的位置上，将它们复制到辅助组B中。 每次从对应B中的两个段取出一个记录进行关键字的比较，将较小者放入A中， 当数组B中有一段超出其表长时(例如B[low,mid]全部被放入A中)，将另一段(例如B[mid,high])中的剩余部分直接复制到A中。
ElemType *B={ElemType *}malloc{(n+1)*sizeof(ElemType)};//辅助数组B
void Merge(ElemType A[],int low,int mid,int high){
//表A的两段A[low...mid]和A[mid+1...hign]各自有序，将它们合并成一个有序表
for(int k=low;K<=high;k++){
B[k]=A[k];//将A中所有元素复制到B中
}
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
if(B[i]<=B[j]) //比较B的左右两段中的元素
A[k]=B[i++];//将较小值复制到A中
else
A[k]=B[j++];
}//for
while(i<=mid)//若第一个表未检测完，复制
A[k++]=B[i++];
while (j<=high)//若第二个表未检测完，复制
A[k++]=B[j++];
}一趟归并排序的操作是，调用[n/(2h)]次算法merge()将L[1...n]中前后相邻且长度为h的有序段进行两两归并，得到前后相邻、长度为2h的有序段， 整个归并排序需进行【log(2)n】趟。 递归形式的2—路归并排序算法是基于分治的，其过程如下： 分解：将含有n个元素的待排序表分成n/2个元素的子表，采用2-路归并排序算法对两个子表进行排序； 合并：合并两个已排序的子表得到排序结果.
void MergeSort(ElemType A[],int low,int high){
if(low<high){
int mid=(low+high)/2;//从中间划分两个子序列
MergeSort(A,low,mid);//对左侧子序列进行递归排序
MergeSort(A,mid+1,high);//对右侧子序列进行递归排序
Merge(A,low,mid,high);//归并
}//if
}初始关键字：【49】，【38】，【65】，【97】，【76】，【13】，【27】 一趟归并后：【38,49】，【65,97】，【76,13】，【27】 二趟归并后：【38 49 65 97】，【13 27 76】
三趟归并后：【13 27 38 49 65 76 97】
MergeSort(A,0,6)
mid=3
MergeSort(A,0,3)//左侧子序列进行递归排序
{
mid=(0+3)/2=1;
MergeSort(A,0,1);//[38,49]
MergeSort(A,2,3);//[65,97]
meger(A,0,3);//[38,49,65,97]
}
MergeSort(A,4,6)//右侧子序列进行递归排序
{
mid=(4+6)/2=5;
MergeSort(A,5,6);
{
mid=(5+6)/2=5;
MergeSort(A,5,5);
MergeSort(A,6,6);
Merge(A,5,5,6);//[13,27]
}
MergeSort(A,6,6);
Merge(A,4,5,6)//[13,27,76]
}
Merge(A,0,3,6)//{13,27,38,49,65,76,97} 最后一次归并
}空间效率:Merge()操作中，辅助空间刚好要占用n个单元，所以归并排序的空间复杂度为O(n) 时间效率:每一趟归并的时间复杂度为O(n),共需进行[log(2)n]趟归并。所以算法的时间复杂度为O(nlog(2)N). 稳定性：由于Merge()操作不会改变相同关键字记录的相对次序，所以2-路归并排序算法是一个稳定的排序。