归并排序

基本思想

分治法。将数组分成两个小数组，对小数组进行归并排序，在合并两个小数组。

具体实现

def merge(nums, p, q, r):
    left = [_ for _ in nums[p:q+1]]
    right = [_ for _ in nums[q+1:r+1]]
    left_len = q - p + 1
    right_len = r - q
    i, j, k = 0, 0, 0
    while i < left_len and j < right_len:
        if left[i] < right[j]:
            nums[p+k] = left[i]
            i += 1
        else:
            nums[p+k] = right[j]
            j += 1
        k += 1
    while i < left_len:
        nums[p+k] = left[i]
        i += 1
        k += 1
    while j < right_len:
        nums[p+k] = right[j]
        j += 1
        k += 1
def _merge_sort(nums, p, r):
    if p < r:
        q = (p + r) // 2
        _merge_sort(nums, p, q)
        _merge_sort(nums, q+1, r)
        merge(nums, p, q, r)
def merge_sort(nums):
    length = len(nums)
    _merge_sort(nums, 0, length-1)

# merge的实现与上面相同
def merge_sort(nums: List):
    length = len(nums)
    step = 1
    while step < length:
        offset = step * 2
        for i in range(0, length, offset):
            merge(nums, i, min(length-1, i+step-1), min(length-1, i+offset-1))
        step *= 2

性能分析

平均时间复杂度：

最坏时间复杂度：

空间复杂度：

• 递归：
• 迭代：

  优化

  在数组比较小时（比如小于20），可以用插入排序代替归并排序，以减小函数调用时间及合并数组时间。