归并排序（MergeSort）的原理及延伸性思考

前面一篇博文写了归并排序的算法实现，虽然做了些注释，但没有写归并排序的原理，这篇就补上，同时对归并所隐含的思想做一个探讨。

1）归并排序的原理

为了便于说明，这里我们提到的已排好序的序列都是指从小到大的升序(对于降序其实原理是一样的。
假设有两个已排好序的序列A,B:
A:a1≤a2≤a3≤...≤an (i:1~n为下标);
B:b1≤b2≤b3≤...≤bm(j:1-m为下标);
如果我们要对A，B进行合并为C，并使得序列C是排好序的,这种情况下就很简单了，我们只要取两个序列的开头进行比较，谁小就取谁，相等任意取一个。然后对剩下的序列继续按照上述原则进行，直到两个序列都取完。比如：
开始：A：{2,5,7,9} B:{3,6,8} C{} ......A的第一个元素2小于B的第一个元素3，则A的第一个元素2入C:
①:A:{5,7,9} B{3,6,8} C{2} ......A的第一个元素5大于B的第一个元素3，则B的第一个元素3入C:
②:A:{5,7,9} B{6,8} C{2,3} ......A的第一个元素5小于B的第一个元素6，则A的第一个元素5入C:
③:A:{7,9} B{6,8} C{2,3,5} ......A的第一个元素7大于B的第一个元素6，则B的第一个元素6入C:
④:A:{7,9} B{8} C{2,3,5,6} ......A的第一个元素7小于B的第一个元素8，则A的第一个元素7入C:
⑤:A:{9} B{8} C{2,3,5,6,7} ......A的第一个元素9大于B的第一个元素8，则B的第一个元素8入C:
⑥:A:{9} B{} C{2,3,5,6,7,8} ......B为空，则把A依次放入C（同理如果A先为空则依次将剩余的B放入C）:
⑦:A:{} B{} C{2,3,5,6,7,8,9} .....排序合并完

上述的过程其实就是归并排序的名称得来，对于已经排好序的序列A(n),B(m),其合并排序时间为T(k)=m+n,属于θ(n)级，是相当快的，但问题是，我们需要排序的序列P(n)未必都是刚好是排好序的两个段(P1[1~m]和P2[m+1~n],而且就是已排好序，你还得去找这个分割点m.那是不是上面讲的这些都白讲了呢？当然不是，这个归并的优势需要结合其它的策略才行。

2）归并排序所蕴含的思想

我们利用归纳法的思想，来思考一下上面所遇到的问题（归纳和演绎是两种非常基本，也非常重要的方法或思想）。
我们从n=1开始分析：
A)如果序列只有一个元素，即n=1，那么归并不存在任何问题;
B)如果序列有2个元素,n=2，利用归并也不存在任何问题，因为m为1，P1[1-1],P2[2-2]两个段显然都是排好序的序列，而且m也很好找，就可以进行归并，也没问题；
C)如果序列有三个元素，n=3,有两种情况：P1[1-1],P2[2-3]和P1[1-2],P2[3-2],这两种情况其实是等价的（其实就是一个段2个元素，一个段1个元素），我们只需要分析一种情况即可。对于只有一个元素的段，我们是可以知道其是排序的，而对于有两个元素的段，就不能确定了，显然也没办法进行归并，但在这里，我们从B可以知道，P2[2-3]本身是可以进行归并的，如果我们先对其进行归并排序，那么P1和P2就可以进行归并了。
D）从C并结合递归的思想，我们发现，对于任意序列P(n),我们总可以对其进行分割，如果分割的两个段不能归并，我们可以分别对两个段各自分割，通过这种方法，我们最终可以将P(n)分割成n个片段，每个片段只包含1个元素，然后两两归并最终完成整个序列的归并排序，这其实就是二分法。通过二分法，我们可以将P(n)做如下分割：

如上图所示，进行二分后，会形成一棵树，每一级的元素个数总数为N,那么每一级的归并T(n)都是θ(n),而深度（树的深度），通过右边深度很容易得出是lg(n)，那么整个归并过程的T(K) =lgK*θ(K)=θ(lgK*K)(K就是n这里为了显示清楚).我们知道插入排序(InsertionSort)的T(K)=θ(K^2),lgK<K,显然，归并排序在K比较大的时候要比插入排序快很多。

3）归并排序的延伸性思考
归并排序采用二分法缩小排序规模，从而利用已排序序列归并算法以实现排序加速。而缩小规模的最基本方法就是N分法（N>1)，二分法是最简单的，当然还有三分法，甚至是N分法，但并不是N越大越好，至于分的时候如何取N,就要看N本身是不是最基本的，对于本例来说，N=2的时候显然可行，对于N=3，那么我们需要对3个序列进行归并排序，每个段的元素（小于等于3个）本身也要排序。（其实归并时候的排序本身就是一个插入排序，而且它是插入排序最理想的情况）。
我们可以观察更为一般的情况，设规模n=K^m【注意这里是为了简化运算，最后会代换回到一般情况】,我们采用K分法,N=K，对于第i级(i=1..m):
有K^(i-1)个片段，每个片段元素数量为K^m/(K^(i-1)=K^(m-i+1)=Ni个元素;但每级元素总数不变，为K^m个.相当于每次从K个元素中取1个最小的，其T(n)=K-1,则一级归并时间是：(K^m * （K-1）),则整体时间为T(n)=(m * K^(m) *（K-1)).因为m=log(K,n),带入上式:T(n)=Log(K,n)*K^Log(K,n)*(K-1)=Log(K,n)*n*(K-1)=(K-1)Log(K,n)*n.从这个表达式可以看出，随着K变大,虽然Log(K,n)可以降低速度,但K却会增加速度。K=2为：lgn * n,K=3时T(n)=2*Log(3,n)*n,n=n时,T(n)=(n-1)*n=θ(n^2),在n分时其实就是插入排序时间复杂度.
上面的情况中我们假设了规模n=K^m,m不一定会是整数，但这个并不影响时间复杂度的判断，原因大家可自己分析。

总结：归并排序利用对于已排序的序列进行排序的最理想情况，并结合N分法思想解决问题，提高效率。N分法思想是降低规模常用的手段，在算法中非常重要，比如查找树之类的(更进一步讲，这就是算法中的分治策略的一种）。一般情况下，二分法就足够了，但在很多规模n非常大的情况下，3分法甚至更高的分法还是有用，不过随着N加大，算法处理的复杂度本身也会加大，因此必须综合权衡。
上述的N分法θ时间表达式是我推理出来的，实际情况中每个分段得元素不太可能正好是相等的，每个片段的元素其实可能在1..Ni中，但我考虑最大情况，就不会影响最后的结论，因为实际情况只可能比考虑的情况好。如果大家觉得上述推理有不妥之处，还望大家指正。

（具体二分法归并，可参见前面的博文）

参考并感谢：网易公开课（麻省理工大学的算法导论课程视频）http://so.v.163.com/movie/listpage/listprogram1/pl2/%BC%C6%CB%E3%BB%FA/default/fc/ot/default/1.html

后记：晚上继续看公开课的第2-3集，看完之后真的汗，别人那是有数学支撑的，虽然我的推论结果是对的，但对于渐进符号，递归解法早就忘了，而我上面说的N分法只是分治策略的一种，看来还是要正规学习。

另外归并排序的递归表达式为：T(n)=2T(n/2)+Θ(c)=θ(nlgn). 其中2表示二分分治后需要处理的策略数。那么对于K分法同样可以表达为(T(n)=KT(n/K)+Θ(c). 大家注意这是K分法的最坏情况，有的时候虽然是K分后，但需要处理的策略并不是等于K，而是小于等于K.比如二分查找的时间递归表达式就是T(n)=T(n/2)+Θ(c)=θ(lgn).