我们来看看归并排序（merge sort）。
def MergeSort(lists):
if len(lists) <= 1:
return lists
num = int( len(lists) / 2 )
left = MergeSort(lists[:num])
right = MergeSort(lists[num:])
return Merge(left, right)
def Merge(left,right):
r, l=0, 0
result=[]
while l<len(left) and r<len(right):
if left[l] <= right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
result += list(left[l:])
result += list(right[r:])
return result
其实归并的主体思想还是很简单的，就是把两个排好序的数组以某种方法放在一起，让他们继续有序。其实归并排序的有难度的地方是递归的过程，当然，在这个算法中递归并不太难，而这种思想有的时候出现的方式很奇妙。
按照CLRS的伪代码，我们可以得到其大致思路：把2个数组末尾放一个很大的数，前边正常比较，小的排列；当某个数组已经达到那个很大的数时，另一个数组的所有数（除了末尾的那个）都会比它小。运算次数的控制就交给向数组中放数的变量，它从最左到最右端，只要它达到了最大，就停止。
那我们来写一下做归并的Merge函数。
template<typename T>
void Merge( T A[ ], int Left, int Center, int Right ) //A为总的数组，其余3个变量为左，中，右
{
n1 = Center - Left + 1; //左数组的总数
n2 = Right - Center;
T *L = new T[ n1 + 1 ];
T *R = new T[ n2 + 1 ];
for ( int n = 0; n != n1; ++n )
L[ n ] = A [ Left + n ];
for ( int n = 0; n != n1; ++n)
R[ n ] = A[ Center + n + 1 ];
L[n1] = 500000; //最后一个数设为很大
R[n2] = 500000;
int i = 0, j = 0, k = Left;
while( k <= Right) //k是控制总排序个数的变量，可以看出k的数量为Right-Left+1，就是本次的总数
if ( L[ i ] <= R [ j ])
A[ k++ ] = L[ i++ ]; //对于小的，让它进入数组的前边，表示已排序
else
A[ k++ ] = R[ j++ ];
delete[ ]L;
delete[ ]R;
}
有一个精妙的地方，就是A[ k++ ] = L[ i++ ];，我们只需要先赋值，再自加，这样写就只用一句话，很简洁。记得C++ primer 5e 里边有说，不需要的时候尽量采用前置自加/自减，因为i++这种后置形式实际上是做完自加后，返回原值，它保存了不必要的变量，同时有时还会引起误解，除非有特别的作用。而这里，就是很叼的“特别的作用”了！记得谭浩强的神题i+++++i吗？如果不想有这种效果，就最好不要使用有误解的写法。
既然说到这里了，我们就顺便复习一下c++的递增/递减运算符重载。我们需要区分一哈后置和前置递增。简单实现一个前置递增：
someClass& someClass::operator++()
{
check(thisNum); //假设有个数是thisNum
++thisNum;
return *this;
}
那么前置呢，为了区分，我们给他一个参数（但不调用）:
somClass someClass::opearator++(int) //这里不使用引用仅仅是因为和内置版本保持一致，返回一个值
{
somClass ret = *this;
++*this;
return ret;
}
这段代码的驱动代码为：
void MergeSort( T *A[ ], int L, int R )
{
if ( p < r )
int center = ( L + R ) / 2;
MergeSort( A, L, Center );
MergeSort( A, Center+1,R );
Merge( A, L, Center, R );
}
不过这个代码也有个问题，就是使用所谓的“哨兵”，在paper里，它可以是无限大∞，可是实现中如何保持它最大呢，如果是固定的类型，比如int，我们尚且可以用INT_MAX，可是泛型呢？怎么办？所以，我们得使用其他的度量方式，那就是数组长度。这一段代码我建议大家自己写写，因为有各种各样的+1，-1，很适合练习一下自己的“逻辑思维”。那么，我们写一下？
首先，我们先写个主程序：
template<typename T>
void MergeSort( T A[ ], int Left, int Right )
{
int Length = Right - Left + 1;
T *tmp = new T[ Length ]; //new一个和原始数组一样长的tmp
if ( tmp != nullptr )
{
if (L < R)
{
int Center = ( L + R ) / 2;
MergeSort( A, Left, Center );
MergeSort( A, Center + 1, Right );
Merge( A, tmp, Left, Center, Right );
}
delete[ ]tmp;
}
}
然后，我们写出它的merge例程：
template<typename T>
void Merge( T A[], T tmp[], int Left, int Center, int Right )
{
int i = Left, j = Center, k = Left;
while ( i != Center + 1 && j != Right + 1 ) //直到有一方为0，则停止循环
if ( A[ i ] <= A[ j ])
tmp[ k++ ] = A[ i++ ];
else
tmp[ k++ ] = A[ j++ ];
//将剩余的放入，哪个剩余放哪个
while ( i != Center + 1 )
tmp[ k++ ] = A[ i++ ];
while ( j != Right + 1 )
tmp[ k++ ] = A[ j++ ];
for ( int i = Left; i != Right + 1; ++i )
A[ i ] = tmp[ i ];
}
这段程序其实很好理解，它的过程分为2段：1）在2个数组都非空之前，让他们比较然后进入tmp；2）当一个子数组全部放入tmp之后，直接把另一个剩余的部分放入tmp就好了，那2个while循环其实只执行一个，但是你完全不需要做判断，因为另一个会因为不满足条件而立刻结束。
现在我们来看看归并排序的时间复杂度。
归并排序把一个问题划分为2个子问题，其中一个大小是不超过N/2的最大整数，一个是超过N/2的最小整数。而这种不影响大方面的问题可以忽略。于是：
T(n)=T(n/2)+T(n/2)+Θ(n)=2T(n/2)+Θ(n)=2T(n/2)+cn
如果画一棵递归树，就会发现：（我不想画啊，去看CLRS啦~~）：
每一棵树有2个分支，每个节点承担n/2的规模大小。这相当于子问题每一层都减少n/2的规模，那么树的高度就是log2n。而每一层的代价是cn，所以总代价为cn*log2n+cn=Θ(nlgn)。
递归树有一个小问题，如果两个子问题不一样怎么办？简单的说，取b小的那条路作为最长路径。你想，b小，说明这个子问题规模大，那它肯定需要被分的更多一些才能到最小情况。
然而每一次都画递归树好像有点麻烦，那么我们再介绍一种有趣的方法，主方法。看上边的式子：T(n)=2T(n/2)+cn，我们可以把它概括为：T(n)=aT(n/b)+f(n)，a代表每一次产生几个子问题，1/b则是每次问题的规模。我们将不证明主定理，只使用，在主观上，它有3种条件下的使用：
1.若f(n)<nlogba，则T(n)=Θ(nlogba)。很好理解，就是一个大，那么它当然占用的时间是更多的。
2.若f(n)=nlogba，则T(n)=Θ(nlogbalgn)
3.若f(n)>nlogba，则T(n)=Θ(f(n));
不过，这不是很对的表述，因为不仅仅要<或者>，是要在多项式意义上<或>，也就是说那些<或>必须要<或>一个量：nε，ε是一个常数。简单的判断方法是做除法，若f/nlogba商是一个必然渐进小于nε的数（如lgn），那么它们不满足主方法条件，还是老老实实用递归树吧~
