归并排序

看了下归并排序，总体来说思想很简单，实现起来也不是很难。

原理

用图说明就好啦，归并排序是基于分而治之的思想，主要分为两步，一步是“分”，另一步是“治”，就是将要排序的列表不断地分解，分解到只有一个元素，然后在进行排序，将排序好的子列表再进行合并。**时间复杂度为O（nlogn）

image.png
image.png

代码

def merge_sort(a_list):
    if len(a_list)<=1:
        return a_list
    if len(a_list)>1:
        mid=len(a_list)//2
        left_half=merge_sort(a_list[:mid])
        right_half=merge_sort(a_list[mid:])
        i=0
        j=0
        res=[]
        while i<len(left_half) and j<len(right_half):
            if left_half[i]<right_half[j]:
                res.append(left_half[i])
                i+=1
            else:
                res.append(right_half[j])
                j+=1
        if i<len(left_half):
            res+=left_half[i:]
            
        if j<len(right_half):
            res+=right_half[j:]
        return res