归并排序

归并排序也用到了递归的思想

还是按照我们的原则，先观察我们想要的输出是什么

显然我们想要的输出是一个排完序的数列

而我们又要一层一层往下分裂到直至每一个子数列都是个数为1或者0

所以我们一开始就要设置分裂停止的条件

def    merge_sort(list):

    n = len(list)

    if n <= 1:

        return list

当我们输入的列表长度小于等于1的时候我们无需进行分裂和后面的排序操作，直接返回它本身

然后我们找到一个中心分裂点

    mid = n//2

    然后递归的部分就来了，递归的思想巧妙就在这

    从结果上看，我们得到的是一个宏观的最后我们默认已经处理好的结果，

    从内部来看，我们是要先不断进行分裂，再进行排序的操作，所以我们把递归写在前面，

    把排序放在后面

    left_li = merge_sort(list[:mid])

    right_li = merge_sort(list[mid:])

    我们深究这个一层层的分裂，先从左边列表不断的进行分裂，直到最后的很小的左列表和右列表长度都小于等于0再进行下面的操作

    从宏观上来说，我们是完成了左右两个列表的排序再进行对整体的排序

    从微观来说，我们是分裂到了极致，再进行排序，递归确实很巧妙。

    下面就是排序了，用left指针和right指针

    left,right = 0,0

    result = []

    while left < len(left_li) and right <len(right_li):

        if left_li[left] < right_li[right]:

            result.append(left_li[left])

        else:

            result.append(right_li[right[)

    然后不管谁走到最后了

    result += left_li[left:]

    result += right_li[right]

    可以看到走到末尾的那一个列表result加上去会是空的

    return result