归并排序空间复杂度疑问：O(n log n)还是O(n)？

这确实是个非常容易混淆的点，我来帮你拆解清楚～

你的疑惑核心在于把「总内存分配量」和「峰值内存占用」搞混了，而通常我们说算法的空间复杂度，指的是后者（即运行过程中同时存在的最大内存开销）。

先再贴一下你的代码方便分析：

def mergeSort(L): 
    N = len(L)
    
    if N <= 1:
        return L
    
    mid = N // 2
    L1 = mergeSort(L[: mid])
    L2 = mergeSort(L[mid :])
    return merge(L1, L2)

为什么你会觉得是O(n logn)？ #

你提到「递归树每一层都用O(n)辅助内存，树有O(logn)层」，这个思路其实计算的是整个递归过程中分配的总内存量：

• 第一层递归会切出两个n/2大小的数组；
• 第二层会切出四个n/4大小的数组；
• 以此类推，直到叶子节点。

把这些内存加起来：n + n/2*2 + n/4*4 + ... +1*n = n logn，这部分总分配量确实是O(n logn)。

为什么网上说空间复杂度是O(n)？ #

这是因为算法分析中默认关注峰值内存占用，而你的代码是深度优先递归，这是关键：

• 代码会先完整处理左子树的所有递归调用，直到左子树完全排序得到L1，此时左子树递归过程中创建的所有临时数组（比如各种切片的子数组）都会被垃圾回收（因为没有引用指向它们了）；
• 之后才会开始处理右子树的递归调用，创建L2，这时候复用的是左子树释放的内存空间；
• 最后merge(L1, L2)需要O(n)的辅助内存（假设merge是创建新的合并数组），加上递归调用栈的O(logn)空间（栈帧本身开销很小），同时存在的最大内存量是O(n)。

补充：两种归并排序的空间差异 #

• 你这种「递归切片+创建新数组」的实现，峰值空间是O(n)，总内存分配量是O(n logn)；
• 如果是原地归并（不创建新的子数组，在原数组上通过辅助空间合并），峰值空间就是O(n)的辅助数组加上O(logn)的栈空间，同样是O(n)；
• 只有当你同时保留所有递归层的子数组（比如并行递归），峰值空间才会达到O(n logn)，但实际递归实现都是深度优先的，不会这么做。

所以网上说的O(n)是指峰值空间复杂度，这是算法分析中通常关注的指标～

内容的提问来源于stack exchange，提问作者Alexandru Oporanu