1.偽代碼

'''MERGE(A,p,q,r)'''
n1 = q - p + 1  //L.length
n2 = r - q      //R.length
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
    R[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算法圖示

2.Python代碼

def merge(A, p, q, r):
    #A[p:q+1]   ,  A[q+1:r+1]
    L = A[p:q+1]
    R = A[q+1:r+1]
    i = 0
    j = 0
    for k in range (p, r+1):
        if i < len(L) and j < len(R):
            if L[i] <= R[j]:
                A[k] = L[I]
                i = i + 1
            else:
                A[k] = R[j]
                j = j + 1
        elif i < len(L):
            A[k] = L[I]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1
    return A

def 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)

result:

Before:
[34, 45, 12, 32, 100, 46, 82, 11]
After:
[11, 12, 32, 34, 45, 46, 82, 100]

循環(huán)不變性對于歸并算法

1. 初始化: 在循環(huán)之前,子數(shù)組為空,L和R數(shù)組升序排列, i=j=1, 分別指向數(shù)組最小值
2. 保持: 每次循環(huán)從L和R中取出當(dāng)前指向兩者中小的值,此值為L和R所有值中的最小值,被取用值的數(shù)組的指針向后指,保證L和R是為歸并的值,此時子數(shù)組升序排列且最大值 <= L和R的最小值
3. 終止: 結(jié)束時 子數(shù)組,L和R數(shù)組均指向數(shù)組最大值,此時子數(shù)組為L和R中的數(shù)值升序排列

歸并算法遞歸部分:MERGE_SORT(A,p,r)

遞歸二分?jǐn)?shù)組,直到p<=r, 即細(xì)分到單元素數(shù)組,所以已經(jīng)排好序.
遞歸歸并子數(shù)組,直到將所有數(shù)據(jù)合并完.

MERGE_SORT算法圖示

歡迎關(guān)注我的博客Vagitus – Pythonista