归并排序

归并排序过程

分解：将待排序的n个元素的序列成各具n/2个元素的两个子序列
解决：使用归并排序递归地排序两个子序列
合并：合并俩个已排序的子序列以产生已排序的答案

图解过程

代码

c版

void merge(int *A, int p, int q, int r) {
    n1 = q - p + 1;
    n2 = r -q;
    int L[length], R[length];
    for(int i = 1; i <= n1; i++) { //前面一半数组
        L[i] = A[p+i-1]
    }
    for(int i = 1; i <= n2; i++) { //后面一般数组
        R[i] = A[q+i]
    }
    int j = k = 1;
    for(int i = p; i <=r; i++) { //数组合并，谁小谁先放
        if(j <= n1 && L[j] < R[k]) {
            A[i] = L[j];
            j = j + 1;
        }
        else {
            A[i] = R[k];
            k = k + 1;
        }
    }
}
void merge_sort(int *A, int p, int r) {
    if(p < r) {
        int q = (p+r) >> 1;
        merge_sort(A, p, q);
        merge_sort(A, q+1, r);
        merge(A, p, q, r);
    }
}

---

python版

def merge(left, right):
    i,j = 0,0
    A = []
    while i < len(left) and j < len(right):
        if left[i] > right[j]:
            A.append(right[j])
            j = j + 1
        else :
            A.append(left[i])
            i = i + 1
    if i == len(left):
        A.extend(right[j:])
    else:
        A.extend(left[i:])
    return A
def merge_sort(A):
    if len(A) <= 1:
        return A
    mid = len(A) // 2
    left = merge_sort(A[:mid])
    right = merge_sort(A[mid:])
    return merge(left, right)

if __name__ == '__main__':
    B = [0,1,3,6,8,3,2]
    print(merge_sort(B))