Python实现归并排序

Python实现归并排序

参考

"""
实现归并排序
"""

l = [2,3,1,4,6,7,1,9]

def merge(a, b):
    rst = []
    while a and b:
        if a[0] <= b[0]:
            rst.append(a.pop(0))
        else:
            rst.append(b.pop(0))
    if a:
        rst += a
    elif b:
        rst += b
    return rst
print(merge([1,2,3,4], [1,6,7,9]))

def merge_sort(l):
    n = len(l)
    if n <= 1:
        return l

    mid = n//2
    left_half = merge_sort(l[:mid])
    right_half = merge_sort(l[mid:])
    return merge(left_half, right_half)

print(merge_sort(l))