基础算法之归并排序

时间复杂度O(nlogn)
运行时间对比：快排<归并<堆排
极端情况下：
快排：极端下效率低
归并：需要额外的内存开销
堆排：在极端快的排序中相对较慢
先分解成2段，然后递归的每一段再分解，直至分解成一个一个的数，然后对比大小排序兵合并为2个数，4个数，8个数这样

def merge(list,low,mid, hight):
    i = low
    j = mid + 1
    tmp = []
    while i <= mid and j <= hight: 
        if list[i] < list[j]:
            tmp.append(list[i])
            i += 1
        else:
            tmp.append(list[j])
            j += 1
    while i <= mid: #若右边没数了，左边还有
        tmp.append(list[i])
        i += 1
    while j <= hight: #若左边没数了，右边还有
        tmp.append(list[j])
        j += 1
    list[low:hight+1] = tmp

def merge_sort(list,low,hight):
    if low< hight:
        mid = (low + hight) // 2 #分解成2段
        merge_sort(list,low,mid) #分解左边那一段
        merge_sort(list,mid+1,hight) #分解右边那一段
        merge(list,low,mid,hight) #排序合并起来，到这一步时已经是一个一个的数了，因为前面已经递归到最深处，所以合并2,4,8，...个数，慢慢往外层合并
abc = list(range(10))
random.shuffle(abc)
print(abc)
merge_sort(abc,0,len(abc)-1)
print(abc)