归并排序适用于向量和列表通用；使用的是分而治之的策略；
归：递归。首先将列表一分为二，并不断递归一分为二；
并：合并，将当前的两个子序列（已有序）合并的算法；
下面是通用的归并排序的模板代码：
template < typename T >
void Vector :: mergeSort(Rank lo, Rank hi) {
if（hi - lo<2）return；//一直递归到子序列是单元素，单元素区间自然有序，否则…
int mi =（lo + hi）>>1；//以中点mi为界
mergeSort(lo, mi)；//对前子序列递归调用本函数mergeSort，对前半段排序
mergeSort(mi, hi)；//对后子序列递归调用本函数mergeSort，对后半段排序
merge(lo, mi, hi)；//归并，将当前的两个子序列（已有序）合并的算法
由上述代码可知，二路归并排序的计算成本T(n) = 2*T(n/2) + O(n)；其中O(n)为函数merge的计算成本；
merge(lo, mi, hi)的基本实现：
merge( )的运行时间主要消耗于for循环，共有两个控制变量j和k
初始：j=0，k=0
最终：j=lb，k=lc
亦即：j+k = lb+lc = hi-lo = n
所以for循环共迭代n次，即merge( )总体迭代不过O(n)次，故二路归并排序的计算成本T(n) = 2 * T(n/2) + O(n)成立。通过计算，二路归并算法复杂度为O(n * logn)。计算思路：T(n)到T(1)共有logn层，每层包含一个复杂度为n的算法（merge( )），所以总的时间复杂度为O(n*logn)。
对于规模为n的向量，归并排序的最优、最坏时间复杂度均为Θ(nlog2n) 。
注意，若两个待归并子序列不等长甚至相差很悬殊，merge( )的复杂度仍为O(n)。