# coding=utf-8
A = [5, 2, 4, 7, 10, 1, 3, 2, 6]


def merge2(A, p, q, r):
    """
    A[p:q]是一个排好序的数组
    A[q:r]是另外一个排好序的数组
    将两个排好序的子数组组成一个总的排好序的数组
    :param A:
    :param p:
    :param q:
    :param r:
    :return:
    """
    n1 = q - p + 1
    n2 = r - q
    L = [-1 for x in range(n1)]
    R = [-1 for x in range(n2)]
    for i in range(0, n1):
        L[i] = A[p + i]
    for j in range(0, n2):
        R[j] = A[q + j + 1]
    i = 0
    j = 0

    for k in range(p, r + 1):
        if i >= n1 and j < n2:  # 当L拍完序R未拍完序的情况
            A[k] = R[j]
            j = j + 1
        elif j >= n2 and i < n1:  # 当R拍完序L未拍完序
            A[k] = L[i]
            i = i + 1
        elif L[i] <= R[j]:
            A[k] = L[i]
            i = i + 1
        else:
            A[k] = R[j]
            j = j + 1

def merge_sort(A, p, r):
    if p < r:
        q = (p + r) / 2
        merge_sort(A, p, q)
        merge_sort(A, q + 1, r)
        merge2(A, p, q, r)
        print A, p, q, r


merge_sort(A, 0, len(A) - 1)
print A