归并排序

平均时间复杂度：O(nlogn)

最佳时间复杂度：O(n)

最差时间复杂度：O(nlogn)

空间复杂度：O(n)

排序方式：In-place

稳定性：稳定

def merge_sort(num1, num2):  # 按大小合并数组
    tmp = []
    low = 0
    high = 0
    while low < len(num1) and high < len(num2):
        if num1[low] < num2[high]:
            tmp.append(num1[low])
            low = low + 1
        else:
            tmp.append(num2[high])
            high = high + 1
    if low == len(tmp):
        for i in num2[high:]:
            tmp.append(i)
    else:
        for i in num1[low:]:
            tmp.append(i)
    return tmp
 
 
def merge(list):  # 划分数组
    if len(list) <= 1:
        return list
    mid = len(list) // 2
    left = merge(list[:mid])
    right = merge(list[mid:])
    return merge_sort(left, right)
 
 
if __name__ == '__main__':
    list = [4, 1, 2, 3]
    num = merge(list)
    print(num)