归并排序比较次数测量接近最坏情况，求原因解析

问题描述 #

为什么我的归并排序比较次数测量结果没接近平均情况（0.74 * n * log2(n)），反而更靠近最坏情况（约0.91 * n * log2(n)）？

已尝试的方案 #

• 使用log替代log2（结果比较次数超过最坏情况）
• 使用随机种子
• 换用不同算法实现
• 将运行时长改为10秒、100秒（原1秒）
• 把步数增加至1000
• 仅统计成功比较的次数（结果低于最优情况）

测量结果图 #

测试代码 #

try:
    from matplotlib import pyplot, ticker
except ModuleNotFoundError:
    print("\nplease pip install matplotlib\n")
    exit(0)
from numpy import log2
from multiprocessing import Process, Manager
from multiprocessing.managers import ListProxy
from numpy import linspace, ndarray
from random import seed, shuffle
SEED: str = "Philip Dutré"
STEPS: int = 100
TIMEOUT: float = 1.0
def merge_sort(a: list[int]) -> int:
    aux: list[int] = [0] * len(a)
    return merge_sort_(a, aux, 0, len(a) - 1)
def merge_sort_(a: list[int], aux: list[int], lo: int, hi: int) -> int:
    if hi <= lo:
        return 0
    mid: int = lo + (hi - lo) // 2
    return merge_sort_(a, aux, lo, mid) + \
    merge_sort_(a, aux, mid + 1, hi) + \
    merge(a, aux, lo, mid, hi)
def merge(a: list[int], aux: list[int], lo: int, mid: int, hi: int) -> int:
    comparisons: int = 0
    for k in range(lo, hi + 1): aux[k] = a[k]
    i: int = lo; j: int = mid + 1
    for k in range(lo, hi + 1):
        if i > mid:             a[k] = aux[j]; j += 1
        elif j > hi:            a[k] = aux[i]; i += 1
        elif aux[j] < aux[i]:   a[k] = aux[j]; j += 1; comparisons += 1
        else:                   a[k] = aux[i]; i += 1; comparisons += 1
    return comparisons
def merge_sort_worst(n: ndarray[float]) -> int:
    return n * log2(n)
def merge_sort_average(n: ndarray[float]) -> int:
    return 0.74 * n * log2(n)
def merge_sort_best(n: ndarray[float]) -> int:
    return n * log2(n) / 2
def run(sizes: ListProxy, comparisons: ListProxy) -> None:
    size: int = 1
    while True:
        arr: list[int] = list(range(size))
        shuffle(arr)
        comparisons.append(merge_sort(arr))
        sizes.append(size)
        size *= 2
def main():
    seed(SEED)
    with Manager() as manager:
        sizes: ListProxy = manager.list()
        comparisons: ListProxy = manager.list()
        process: Process = Process(target=run, args=(sizes, comparisons))
        process.start()
        process.join(timeout=TIMEOUT)
        process.terminate()
        n: ndarray[float] = linspace(1, sizes[-1], STEPS)
        pyplot.figure(num=f'Merge Sort')
        pyplot.title(f'Merge Sort (seed: {SEED}, {STEPS} steps, {TIMEOUT} sec)')
        pyplot.xlabel('# Elements')
        pyplot.ylabel('# Comparisons')
        formatter = ticker.StrMethodFormatter("{x:,.0f}")
        pyplot.gca().xaxis.set_major_formatter(formatter)
        pyplot.gca().yaxis.set_major_formatter(formatter)
        pyplot.scatter(sizes, comparisons, label="Measurements")
        pyplot.plot(n, merge_sort_average(n), label="Average Case (~0.74nlgn)", linestyle='dotted')
        pyplot.plot(n, merge_sort_best(n), label="Best Case (~nlgn/2)", linestyle='dotted')
        pyplot.plot(n, merge_sort_worst(n), label="Worst Case (~nlgn)", linestyle='dotted')
        pyplot.legend()
        pyplot.show()
if __name__ == "__main__":
    main()

问题根源与解决办法 #

1. 平均情况公式完全错误 #

你用的0.74 * n * log2(n)是快速排序的平均比较次数近似值，并非归并排序的。归并排序的比较次数特性如下：

• 最坏情况：n log2(n) - n + 1（输入完全逆序时）
• 平均情况：~n log2(n) - 1.44n（随机输入的期望次数）
• 最好情况：~n log2(n)/2（输入已经有序时）

当n较大时，n log2(n)项占绝对主导，平均情况和最坏情况的曲线几乎重合，低阶项的差异可以忽略——这就是你的测量结果接近最坏情况的核心原因。

2. 验证你的计数逻辑 #

你的比较计数是正确的：仅在实际执行aux[j] < aux[i]比较时计数，数组耗尽时的直接复制不计数，符合标准的归并排序比较次数统计方式。之前尝试“仅统计成功比较”的操作反而会导致计数偏低，因为else分支同样是一次有效比较（判断aux[j] >= aux[i]）。

修正后的平均情况函数 #

把merge_sort_average改成如下，绘图后测量点会落在平均与最坏情况之间，符合预期：

def merge_sort_average(n: ndarray[float]) -> ndarray[float]:
    return n * log2(n) - 1.44 * n

额外说明 #

归并排序的比较次数波动远小于快速排序，无论输入是否随机，比较次数都集中在n log2(n)附近，这是归并排序的固有特性——它是稳定的比较排序，时间复杂度的常数因子几乎固定。

内容的提问来源于stack exchange，提问作者Nice Zombies