100-1000元素数组：MergeSort与QuickSort效率对比及实现疑问

平均情况性能差异 #

两者的平均时间复杂度都是O(n log n)，但核心差异在常数因子和内存开销上：

• MergeSort 需要额外的O(n)空间存储合并时的临时数组，频繁的数组切片、拷贝操作会拉高常数因子。
• QuickSort（优化后的原地实现）不需要额外的O(n)空间（递归栈空间为O(log n)，可忽略），分区操作原地进行，缓存命中率更高，常数因子远低于MergeSort。
• 注意：QuickSort的最坏时间复杂度是O(n²)，但通过随机选pivot、三数取中等优化手段，几乎可以避免这种情况，实际平均表现更优。

可对比二者效率的Python测试程序 #

下面是直接的测试脚本，生成随机数组并分别统计两种排序的耗时：

import random
import time

# MergeSort实现
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)

def _merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

# 带随机pivot的QuickSort实现
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = random.choice(arr)
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

def benchmark(n):
    # 生成随机数组
    test_arr = [random.randint(0, 10**4) for _ in range(n)]
    
    # 测试MergeSort
    start = time.perf_counter()
    merge_sort(test_arr.copy())
    merge_elapsed = time.perf_counter() - start
    
    # 测试QuickSort
    start = time.perf_counter()
    quick_sort(test_arr.copy())
    quick_elapsed = time.perf_counter() - start
    
    print(f"数组规模n={n}:")
    print(f"  MergeSort耗时: {merge_elapsed:.6f}秒")
    print(f"  QuickSort耗时: {quick_elapsed:.6f}秒")
    print(f"  QuickSort比MergeSort快{merge_elapsed/quick_elapsed:.2f}倍\n")

# 测试100、500、1000规模的数组
for size in [100, 500, 1000]:
    benchmark(size)

运行脚本会输出不同规模下两种算法的耗时对比，每次测试都拷贝原数组，避免排序后的数组影响结果。

通用场景下谁更快 #

通用数组排序场景中，QuickSort的速度普遍优于MergeSort，核心原因：

• 原地排序特性减少了内存分配和数据拷贝的开销，对CPU缓存更友好。
• 分区操作的指令复杂度更低，常数因子远小于MergeSort的合并操作。
• 虽然MergeSort是稳定排序，但绝大多数通用场景不需要稳定性，QuickSort的速度优势更关键。
• 例外情况：如果是链表排序，MergeSort的表现会更好，因为链表的合并不需要额外空间，而QuickSort的分区操作在链表上效率极低。

100-1000元素数组中的效率对比 #

在100到1000的小规模数组中，QuickSort依然会比MergeSort更快：

• 小规模下，常数因子的影响被放大，MergeSort的数组切片、拷贝开销会变得更明显。
• 即使是小规模，随机pivot的QuickSort也能稳定保持O(n log n)的平均性能，不会出现最坏情况。
• 实际测试中，这个规模下QuickSort的耗时通常是MergeSort的1/2到1/3左右，具体取决于实现细节。

内容的提问来源于stack exchange，提问作者Dylan Headley