归并排序稳定性分析

归并排序稳不稳定关键要看 merge() 函数，也就是两个有序子数组合并成一个有序数组的那部分代码。在合并的过程中，如果 A[p…m]和 A[m+1…r]之间有值相同的元素，那我们可以像伪代码中那样，先把 A[p…q]中的元素放入 tmp 数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。

def merge(lst1, lst2):  # 有序列表lst1 lst2 合并成lst3
    lst3 = []
    i1, i2 = 0, 0  # 追踪每个列表当前的位置
    n1, n2 = len(lst1), len(lst2)
    while i1 < n1 and i2 < n2:  # lst1 和lst2 都拥有更多元素
        if lst1[i1] < lst2[i2]:  # lst1 的第一个元素更小
            lst3.append(lst1[i1])  # 把这个小的追加到临时列表
            i1 = i1 + 1
        else:  # lst2 的第一个元素更小
            lst3.append(lst2[i2])
            i2 = i2 + 1
    if i1 == n1:
        for i in lst2[i2:]:
            lst3.append(i)
    else:
        for i in lst1[i1:]:
            lst3.append(i)
    return lst3


def mergeSort(nums):
    n = len(nums)
    if n <= 1:
        return nums
    m = n // 2
    left = mergeSort(nums[:m])
    right = mergeSort(nums[m:])
    return merge(left, right)


print(mergeSort([1, 3, 2, 4, 5, 7, 9,2]))

总结

• 先操作左半部分,再操作右半部分,归并排序就是稳定的