# __author:   han-zhang
# date:  2019/1/25 19:29

def merge(a, b):
    c = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1

    # 如果i已经移出去了，而j还未移完，则遍历j的后半部分，一次追加，反之亦然
    if i == len(a):
        for k in b[j:]:
            c.append(k)
    else:
        for h in a[i:]:
            c.append(h)
    return c


def merge_sort(lists):
    if len(lists) <= 1:
        return lists
    middle = len(lists) // 2
    left = merge_sort(lists[:middle])
    right = merge_sort(lists[middle:])
    print("left", left)
    print("right", right)
    return merge(left, right)


if __name__ == "__main__":
    nums = [9, -2, 7, 5, 3, 7, 4, 8, 3, 2, 1]
    nums1 = merge_sort(nums)
    print(nums1)