归并排序
时间O(nlogn),空间O(n)

#python
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
    
    c += a[i:]
    c += b[j:]

    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:])
    return merge(left, right)


if __name__ == '__main__':
    a = [4, 7, 8, 3, 5, 9,1]
    print (merge_sort(a))
    #[1, 3, 4, 5, 7, 8, 9]