递归与分治-归并排序

递归算法是直接或者间接不断反复调用自身来达到解决问题的方法。这就要求原始问题可以分解成相同问题的子问题。而分治（divide and conquer ，D&C）就是将待解决复杂的问题能够简化为几个若干个小规模相同的问题，然后逐步划分，达到易于解决的程度。

分治算法适用问题的特征有

•   该问题的规模缩小到一定的程度就可以容易地解决

•    该问题可以分解为若干个规模较小的相同问题 、子问题规模相同

•  该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题

因此，递归算法和分治算法可以说是相得益彰。

归并排序（又称合并排序）是分治算法的一个完美列子。它的基本思想是对于一个需要排序的数组，算法首先把它分为两个部分，并对每个子数组进行递归排序（将子序列继续分解，直到子序列包含的元素个数为1，因为单个元素的序列本身是有序的），最后把这两个排序好的子数组合并为一个有序数组。如下一个数组的排序的例子

不难写出伪代码如下

mergesort(alist):

              n= len(alist)

              if n>1:

                    copyalist[0:n//2+1] to blist

                    copyalist[n//2+1:n] to clist

               mergesort(blist)

               mergesort(clist)

               merge(blist,clist,alist)

       其中merge方法是合并算法，目的是将分解后的排序好的子数组进行合并排序。

       该算法中用两个指针（下标）分别指向两个待合并数组的第一个元素，然后比较这两个元素的大小，将较小的元素添加到一个新创建的辅助数组中，接着被复制数组中的指针后移，指向下一个元素，上述操作一直持续到两个数组中有一个被先处理完毕为止，然后在未处理完的数组中，剩下的元素被复制到新数组的尾部即可。如

故python实现代码为

def mergesort(alist):

    length=len(alist)

    if length<=1:         #基础条件，只有一个元素时

       return

    else:

        blist=alist[0:length//2]

        clist=alist[length//2::]

         mergesort(blist)

        mergesort(clist)

        merge(blist,clist,alist)

def merge(blist,clist,tlist):

     blen=len(blist)

    clen=len(clist)

    bi=ci=k=0

    while bi排序

        if blist[bi]<=clist[ci]:

            tlist[k]=blist[bi];

            bi+=1

        else:

            tlist[k]=clist[ci];

            ci+=1

        k=k+1

    tlist[k:blen+clen]= bi==blen and clist[ci:clen] or blist[bi:blen]        #blist先遍历完，clist直接追加到tlist

       测试用例

>>> alist=[2,1]

>>> mergesort(alist)

>>> alist

[1, 2]

>>> alist=[2,1,0,5,3]

>>> mergesort(alist)

>>> alist

[0, 1, 2, 3, 5]

>>> 

       合并排序的时间复杂度与快速排序一样。只不过需要额外的存储空间来进行合并，每调用一次合并算法，都需要临时分配一个适当大小的辅助存储区，最多分配大小为n。因为递归调用时占用的帧空间是递归树的深度n=[if !msEquation] [endif]，则x=logn，递归树的深度是logn。