归并排序 mergeSort

把序列按长度分成两个子序列，每个子序列再次分解，重复以上操作直至无法分解（递归从外到内的过程）
把两个最小单位的子序列按条件归并成一个新序列，新序列继续和同一层的序列归并（递归从内到外的过程）
使用两个指针从被归并的两个序列中分别取值比较大小，取出满足条件的值并移动该指针，然后进行下一次比较
利用map()、reduce()进行拆解和合并的过程
需要消耗大量空间

复杂度：最优时间复杂度：O(nlogn)
        最差时间复杂度：O(nlogn)
        稳定性：稳定

def merge_sort(varlist):
    # 结束递归的条件，子序列被分解为单个元素
    if len(varlist) <= 1 :
        return varlist

    # 1.第一步：把完整的序列分解为单个元素的序列，然后作为参数调用归并两两排序

    # 将序列按长度等分
    num = len(varlist) // 2
    l_left = varlist[:num]
    l_right = varlist[num:]

    # 分解后的两个子序列调用自身继续分解，直至被分解为单个元素
    left = merge_sort(l_left)
    right = merge_sort(l_right)

    # 当出现left和right都为单个元素时，递归从外向内的过程结束，开始归并
    return merge(left,right)

def merge(left,right):
    # 2.第二步：从传入的两个序列中，按顺序各取出一个元素比较大小
    # 把满足排序条件的取出放入空list，不满足的等待下一次比较，直至任一序列中元素被取完

    # l和r指针用来标记从left和right中取值的位置
    l,r = 0,0
    # 空list用来存放排序后的结果，排序完成则return
    reslist = []

    # l增加到与left长度相等，或r增加到与right长度相等，表示该序列被遍历完成，结束循环
    while l < len(left) and r < len(right) :

        # 从两个序列中各取出一个值进行比较，把满足条件的放入新序列，并移动指针
        if left[l] < right[r] :
            reslist.append(left[l])
            l += 1
        else :
            reslist.append(right[r])
            r += 1

    # 把另一序列中剩余的元素全部添加到新序列
    # 此时另一个序列中无论剩余多少元素没被取出，都一定是在前一层归并中排好序的
    reslist += left[l:]
    reslist += right[r:]

    return reslist

varl = [5,1,7,5,6,3,4,8,2,3,5,9]
res = merge_sort(varl)
print(res)

[1, 2, 3, 3, 4, 5, 5, 5, 6, 7, 8, 9]