归并排序：为什么它稳定又保证 O(n log n)

归并排序是分治思想最教科书式的实现：把数组不断对半切开到单元素（天然有序），再自底向上把两个有序子数组合并成更大的有序数组。它有两个让它在工程界长盛不衰的性质——稳定，以及无论最好/平均/最坏都是 O(n log n)。

图：归并排序的“分—合”递归结构（以 [5,2,4,6,1,3,2,8] 为例）

合并（merge）是整个算法的核心：给定两个已排序的子数组，用两个指针 i、j 分别扫描，每次把较小者写入结果，直到一侧耗尽，再把另一侧整体追加。整个过程每个元素只被比较、写入常数次。

图：merge(L,R) 双指针合并——每次取较小者写入 temp

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:   # 相等时取左侧 → 稳定
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])        # 左侧剩余
    result.extend(right[j:])       # 右侧剩余
    return result

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # 分
    right = merge_sort(arr[mid:])  # 分
    return merge(left, right)      # 合

复杂度用主定理一眼看穿：递推式 T(n) = 2T(n/2) + Θ(n)，其中 a=b=2，临界值 n^{log₂2} = n，而合并代价 f(n)=Θ(n) 与临界值同阶（情况 2），于是 T(n)=Θ(n log n)。注意这是最坏情况也成立的界，不像快排会退化到 O(n²)。

import math
def merge_sort_compare_count(arr):
    # 返回 (排序结果, 比较次数)，用于实测 O(n log n)
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    l, c1 = merge_sort_compare_count(arr[:mid])
    r, c2 = merge_sort_compare_count(arr[mid:])
    res, c3 = merge_count(l, r)
    return res, c1 + c2 + c3

def merge_count(left, right):
    result = []; i = j = c = 0
    while i < len(left) and j < len(right):
        c += 1
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:]); result.extend(right[j:])
    return result, c + (len(left) - i) + (len(right) - j)

# 8 个元素最坏比较次数 = 8*log2(8) - (8-1) = 24 - 7 = 17
print(merge_sort_compare_count([5,2,4,6,1,3,2,8])[1])  # 17

稳定性来自合并时的“相等取左侧”规则：当 left[i] == right[j]，先取左侧元素，相等键的原始相对顺序被保留。代价是合并需要长度 O(n) 的辅助数组，因此空间复杂度 Θ(n)，不是原地排序——这正是它相比快排/堆排更吃内存的原因。