# 5. 归并排序
基本思想
1）把 n 个记录看成 n 个长度为 l 的有序子表；
2）进行两两归并使记录关键字有序，得到［n/2］个长度为 2 的有序子表；
3）重复第（2）步，直到所有记录归并成一个长度为 n 的有序表为止。
// 相邻两个有序子序列的合并成算法 | |
/* 已知 r1 [low..mid] 和 r1 [mid+1..high] 分别按关键字有序排列，将它们合并成一个有序序列，存放在 r2 [low..high] */ | |
void Merge ( RecordType r1[], int low, int mid, int high, RecordType r2[]){ | |
i=low;j=mid+1; k=low; | |
while ( (i<=mid)&&(j<=high) ){ | |
if ( r1[i].key<=r1[j].key ){ | |
r2[k]=r1[i] ; ++i; | |
}else{ | |
r2[k]=r1[j] ; ++j; | |
} | |
++k ; | |
} | |
while( i<=mid ){ | |
r2[k]=r1[i]; | |
k++; | |
i++; | |
} | |
while( j<=high){ | |
r2[k]=r1[j]; | |
k++; | |
j++; | |
} | |
} /* Merge */ |
性能分析：
空间复杂度：O (n)
时间复杂度：O (nlog2n)
稳定
