递归排序一个数组：
递归排序总过程：
图片说明
merge过程：
图片说明 

# 主函数，传递数组
def mergeSort(arr):
    if arr and len(arr) < 2:
        return arr
    process(arr, 0, len(arr) - 1)
    return arr


# 把arr[L....R]上排好序（递归），调用merge（合并）方法
def process(arr, L, R):
    # base case：
    if L == R:
        return arr
    mid = L + ((R - L) >> 1)
    process(arr, L, mid)
    process(arr, mid + 1, R)
    merge(arr, L, mid, R)


# 创建一个空数组，将process方法排序好的两个数组，谁小，追加到末尾
def merge(arr, L, M, R):
    help = []
    i, p1, p2 = 0, L, M + 1
    while p1 <= M and p2 <= R:
        if arr[p1] <= arr[p2]:
            # 谁小追加到help数组末尾
            help.append(arr[p1])
            p1 += 1
        else:
            help.append(arr[p2])
            p2 += 1
        i += 1
    while p1 <= M:
        help.append(arr[p1])
        i += 1
        p1 += 1
    while p2 <= R:
        help.append(arr[p2])
        i += 1
        p2 += 1
    # 将help数组中已排序好的数组，修改进arr中    
    for i in range(len(help)):
        arr[L + i] = help[i]


arr = [3, 2, 4, 6, 8, 9, 6, 42, 13, 4, 56, 65]
ans = mergeSort(arr)
print(ans)