Merge Sort

废话不多说，先上伪代码

Merge(A, p, q, r)
    n1 = q - p + 1
    n2 = r -q
    Let L[1..n1+1] and R[1..n2 +1] be new arrays
    for i = 1 to n1
        L[i] = A[p+i-1]
    for j = 1 to n2
        L[j] = A[q+j]
    L[n1+1] = ∝
    R[n2+1] = ∝
    i = 1
    j = 1
    for k = p to r
        if L[i] ≤ R[j]
             A[k] = L[i]
             i = i + 1
        else
            A[k] = R[j]
            j = j + 1


Merge_sort(A, p, r)
    if p < r
        q = ⌊(p+r)/2⌋
    Merge_sort(A, p, q)
    Merge_sort(A, q+1, r)
    Merge(A, p, q, r)

Merge sort 采用分治思想来排序，一组数据对半分成两组， L1与L2，分别对L1与L2再分成两组。递归调用merge_sort函数，直到每一组只剩一个元素。一个元素，自然是有序的。递归回调时，把这些元素一个一个组装起来即可。组装的过程就是调用merge函数，重点是for k = p to r这一段。


对于分治思想，《Introduction To Algorithms》书上原文如下：

The merge sort algorithm closely follows the divide-and-conquer paradigm, Intuitively, it operates as follows
Divide: Divide the n-element sequence to be sorted into wto subsequences of n/2 elements each.
Conquer: Sort the two subsequences recusrively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.

Merge_sort函数相当于divide, Merge_sort(A, p, q)是对左边递归分组， Merge_sort(A,q+1, r)是对右边递归分组。一直递归到每组只剩一个元素（有序，conquer）就开始合并（combine）。即分完之后是治，治后是合。合并的函数是Merge(A, p, q, r)
用扑克牌来作个形象的说明。8张扑克牌，黑桃2~9，打乱顺序，合并放桌上。第一次是一堆，开始divide，分成2堆，2堆分4堆，4堆分8堆。治的第一轮，A[1]与A[2]、A[3]与A[4]、A[5]与A[6]、A[7]与A[8]分别比较合并。之后A[1, 2]、A[3, 4]、A[5, 6]、A[7, 8]都是有序的。Merge_sort后再一次回调合并。A[1, 2, 3, 4]与A[5, 6, 7, 8]都是有序，最后一次合并A[1~8]都有序。
列表图说明如下：

• 黑线上方是分的过程，下方是合的过程。
• 横向是治，比较完大小后转入上一层递归回调。

在Merge过程中有一个conquer，便是治的问题，可以这样理解。当牌分成8堆，拿第1、2堆两张比较，小的放左边，两两比较合并成4堆。对于4堆2张牌，第1堆拿最左边那张，在第1、2堆左边选出最小的，交替拿完3张。至此，4堆变2堆，重复上一个过程，2堆变1堆。这个拿牌合并的过程，相当于伪代码中for k = p to r的这套循环。

Python代码如下：

def merge(ml, p, q, r):
    L = ml[p:q]      # 对原始数据，左右两边各复制一份，保留。用于之后比较与下方的for循环，类似于交换数据。
    R = ml[q:r]
    L.append(float('inf'))       # 设置哨兵值，其值是正无穷
    R.append(float('inf'))
    i = j = 0
    for n in  range(p, r):       # 对于分好堆的牌，开始抓牌合并
        if L[i] <= R[j]:         
            ml[n] = L[i]
            i = i + 1
        else:
            ml[n] = R[j]
            j = j + 1
    return ml


def merge_sort(ml, p, r):
    if p+1 < r:
        q = (p + r) // 2
        merge_sort(ml, p, q)
        merge_sort(ml, q, r)
        merge(ml, p, q, r)

    return ml

slist = [5, 2, 4, 7, 8, 3, 9, 6]
mslist = merge_sort(slist, 0, len(slist))
print(mslist)

初次调用merger sort 排序显示的结果不正常，只有[2, 4, 5,]这几个数字，关于merge函数，最开始的代码如下：

def merge(ml, p, q, r):
    nleft = q - p
    nright = r - q
    L = ml[:nleft]
    R = ml[nright:r]

若是如此，最终替换的都是前三个数。merge sort的主要思想是分组、比较、合并。最终是分成8堆，即，要保存L=[i](i = 2k,k=0,1, 2)、R=[j](j=2k+1, k=0,1,2)，比较后分别替换mlx这8个数。分析明白后，把这4行代码替换成L=ml[p:q]与R=[q:r]即可。

现说明为何需要添加哨兵值，以及merge函数中for n in range(p, r):的思想。当merge_sort递归到最深的一层是，L与R都只有两个元素，另inf=float('inf')，表示正无穷，L=[5, inf]， R=[2, inf]。此时p=0，r=2，即n=[0, 1]， 第一次比较合并是合并列表前两个元素。i = j = n = 0时，5<2， 不成立，即ml[0]=2， j=1。进入下一层for循环，此时R[1]=inf，把5添加到ml[1]的位置。

这个过程相当于桌面两张牌，选出最小的那张放左手最左边，然后再从另外一堆抓一张放左手。若堆里有2张及以上的牌，从L与R中选一张最小的放左手，设L中取最小，第二张牌就是从R中取，第三张又是L中取。如此，交替，取完两堆的牌。

第一次取最小，是对应L[i] <= R[j]，表明升序。第一次取最大，是对应L[i] >= R[j]，表明降序。