• 动画演示：https://www.runoob.com/python3/python-merge-sort.html

  • 算法分析：
    将归并排序分为两个过程来分析：分裂和归并。

    1. 分裂的过程，借鉴二分查找中的分析结果，是对数复杂度，时间复杂度是O(log n)
    2. 归并的过程，相对于分裂的每个部分，其所有数据项都会被比较和放置一次，所以是线性复杂度，其时间复杂度是O(n)

综合考虑，每次分裂都进行一次 O(n)的数据项合并，总的时间复杂度是O(nlog n)

  • 使用了额外1倍的存储空间用于归并，这个特性在对特大数据集进行排序的时候要考虑进去。
  • 代码中的切片操作，可以改为传递两个分裂部分的起始点和终止点，以减少时间复杂度。 
def mergeSort(alist):
    #递归结束条件
    if len(alist) <= 1:
        return alist
    #分解问题，并递归调用
    middle = len(alist) // 2
    left = mergeSort(alist[:middle])
    right = mergeSort(alist[middle:])
    #合并左右半部，完成排序
    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))
    merged.extend(right if right else left)
    return merged