归并排序

参考：

归并排序(图文并茂)

归并排序(动图理解)

# mergesort
"""
1、merge_sort函数把一个列表分成两部分，每一个部分继续二分，递归下去，直到列表里只有1个元素
2、然后将各自只有1个元素的两个列表传递给merge函数，比较大小构建成有序的列表
3、依次按照1中递归的顺序返回2中列表，不断的合并，最后得到排序好的数组
"""


def merge_sort(li):
    if len(li) == 1:
        return li

    # 把数据拆分成左右各一半
    mid = n // 2
    left = li[:mid]
    right = li[mid:]

    # 继续递归拆分
    l_res = merge_sort(left)
    r_res = merge_sort(right)

    # 把下层方法返回的两个有序序列，再组成有序
    res = merge(l_res, r_res)
    return res


def merge(ll, rl):
    """把两个有序序列，再组成有序"""
    # [1] [2]
    # [1,2] [3,6]

    # 两个下标分别指向两个序列的0位置
    l_index = 0
    r_index = 0

    # 创建临时列表存放结果
    res = []
    while l_index < len(ll) and r_index < len(rl):
        if ll[l_index] <= rl[r_index]:  # 等号保证稳定性
            res.append(ll[l_index])
            l_index += 1
        else:
            res.append(rl[r_index])
            r_index += 1
    # 循环结束时，只能把其中一个列表的数据全部放到结果中
    res += ll[l_index:]
    res += rl[r_index:]
    return res


if __name__ == '__main__':
    l = [4, 2, 3, 5, 1]
    l = [5, 4, 3, 2, 1]
    print(merge_sort(l))
    # l=[2,4,6,7,8]
    # r=[1,3,5]
    # # 1,2,3,4,5
    # print(merge(l,r))

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