归并排序

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
将数组分解最小之后，依次合并两个有序数组。基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位；然后再比较，直至一个数组为空，最后把另一个数组的剩余部分追加。

归并排序的分析

快速排序传入本身列表，通过控制操作范围达成排序目的
归并排序则传入原序列切片后生成的新的子序列

def merge_sort(alist):
    '''归并排序'''
    '''对列表进行拆分'''
    n = len(alist)
    # 1.先将列表进行拆分，直至拆分到每个分组只有一个元素
    if n <= 1:  # 递归终止条件
        return alist  # 当序列只有一个值时无需排序，直接返回序列本身
    else:
        mid = n // 2
        # 此时将列表分成两个部分
        left_li = merge_sort(alist[mid:])  # 对拆分后的部分再调用归并排序，返回left_li和right_li是有序的新列表
        right_li = merge_sort(alist[:mid])
        '''对列表进行合并'''
        left_pointer, right_pointer = 0, 0
        # 2.将两个有序的子序列，合并成一个新的整体
        result = []  # 子序列合并后为一新列表，建一个空列表用于存储
        while left_pointer < len(left_li) and right_pointer < len(right_li):
            if left_li[left_pointer] <= right_li[right_pointer]:
                result.append(left_li[left_pointer])
                left_pointer += 1
            else:
                result.append(right_li[right_pointer])
                right_pointer += 1
        # 当退出循环体时，左右两个部分至少有一个指针已遍历完，则在整体后追加另一边游标未处理的剩余数据
        result.extend(left_li[left_pointer:])  # 列表.extend(列表)，直接在原对象上追加新列表，不生成新对象占用空间
        result.extend(right_li[right_pointer:])  # 对一个列表，当超出列表长度进行切片，则返回一个空列表，不报错
        return result  # 返回新对象result

测试

if __name__ == '__main__':
    li = [54, 26, 93, 17, 77, 31, 44, 55]
    print(li)
    sorted_li = merge_sort(li)  # 归并排序的返回值为一个已排序的新列表，不对原列表本身排序
    print(li)
    print(sorted_li)

执行结果：
[54, 26, 93, 17, 77, 31, 44, 55]
[54, 26, 93, 17, 77, 31, 44, 55]
[17, 26, 31, 44, 54, 55, 77, 93]

归并函数代码执行顺序

缩进代表在一个递归函数内

1.merge_sort([54, 26, 93, 17, 77, 31, 44, 55])
# 运行到left_li = merge_sort(alist[mid:])
    2.left1_li = merge_sort([54, 26, 93, 17])  # 递归函数，打开下层函数搁置一边
        3.left2_li = merge_sort([54, 26])
            4.left3_li = merge_sort([54])  # 再调用函数时，得到第一个返回值[54]
            # 回到上一步搁置代码处，继续执行该循环体中的下行代码：right_li = merge_sort(alist[:mid])right2_li = merge_sort([54,26][1:])
            5.right3_li = merge_sort([26])  # 返回值[26]，关闭最里层递归函数
        6.result = [26, 54] # 此时merge_sort([54, 26])继续执行向下执行result循环体部分,进行合并
        7.right2_li = merge_sort([93, 17])
            8.left3_li = merge_sort([93])
            9.right3_li = merge_sort([17])
        10.result = [17, 93]
    11.result = [17, 26, 54, 93]
    12.right_li = merge_sort([77, 31, 44, 55])
        13.left2_li = merge_sort([77, 31])
            14.left3_li = merge_sort([77]) 
            15.right3_li = merge_sort([31]) 
        16.result = [31, 77]
        17.right2_li = merge_sort([44, 55])
            18.left3_li = merge_sort([44])
            19.right3_li = merge_sort([55])
        20.result = [44, 55]
    21.result = [31, 44, 55, 77]
22.result = [17, 20, 26, 31, 44, 54, 55, 77, 93]

时间复杂度

归并排序代码，对序列的拆分是顺序结构时间复杂度为O(1)。进入合并部分代码后为循环体层级数与层级做乘法运算；每一层级级合并都是顺序执行的，对应的时间复杂度做加运算。每一级数据的合并都要经过两两之间条件对比，时间复杂度为O(n)；合并的层级次数2^x=n，即x=log2(n)，时间复杂度O(logn)。
与快速排序不同对归并排序，永远从中轴线开始拆分，不存在分割线严重偏离的情况，所以最坏时间复杂度还是O(nlogn)。
通过条件if left_li[left_pointer] <= right_li[right_pointer]，考虑等号可以确保排序的稳定性。
整体时间复杂度O(nlogn)

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

归并排序是冒泡、选择、插入、希尔、快速这些排序中最坏时间复杂度最小的，最坏时间复杂度为O(nlogn)。但归并排序返回的是一个排序后的新列表，占用了两份列表空间（原无序列表+新有序列表）。

常见排序算法效率比较

至少会写3种排序算法，快速排序常用必需会！
快速排序平均时间复杂度为O(nlogn)，且不需要额外的存储空间。