一、算法思路：
分治策略：向量与列表通用
序列一分为二 // O(1)
子序列递归排序 // 2 x T(n/2)
合并有序子序列 // O(n)
二、举例如下：
T（n） = 2*T(n/2) + O(n) T(n) = O(nlog(n)) 利用替换法即可求解；其中O(n)是归并两个已排序子序列的时间。
二路归并merge原理如下所示：
二路归并merge实现如下：
开辟空间B来存储_elem[lo,mi)中的元素，而_elem[mi，hi)的元素并不需要开辟新的空间来缓存，只需要定义一个指针C指向这段内存就可以了。
二路归并的再次改进：
因为C是位于A的后半段，当B完全耗尽时，不需要在执行A[i++] = C[k++]; 所以不需要等待C耗尽，一旦B耗尽，就终止。所以交换循环体内两句的次序，删除冗余逻辑。
二路归并的复杂度： 将j+k作为一个整体来看，最坏情况下，只需要O(n)的线性时间。
原文：https://www.cnblogs.com/ccpang/p/11416256.html