归并排序要额外空间：它为什么不是原地排序

归并排序的“合”阶段必须借助一个临时数组存放合并结果，再拷回原数组。

图：归并排序的合并阶段必须借助长度 O(n) 的辅助数组

# 空间 = 递归栈深 O(log n) + 每层辅助数组总长 O(n) ⇒ 总 Θ(n)
# 想做成原地归并并非不可能，但需复杂的“原地合并”技巧，常数大、少用
def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr)//2
    # 注意：下面仍借助返回的列表（隐式辅助空间）
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

这正是归并排序相比快排/堆排更费内存的根因。在内存敏感的嵌入式场景，常改用堆排序（原地）。但对链表，归并可只靠指针调整，几乎不额外占空间。

相关推荐：主定理与空间 · 分治思想