两种Merge Sort版本的辅助空间复杂度是否存在差异？

两种归并排序实现 #

版本1：提前创建左右拆分列表 #

def merge_sort(items):
  if len(items) <= 1:
    return items

  middle_index = len(items) // 2
  left_split = items[:middle_index]
  right_split = items[middle_index:]

  left_sorted = merge_sort(left_split)
  right_sorted = merge_sort(right_split)

  return merge(left_sorted, right_sorted)

版本2：递归时直接传入拆分切片 #

def merge_sort(items):
  if len(items) <= 1:
    return items

  middle_index = len(items) // 2

  left_sorted = merge_sort(items[:middle_index])
  right_sorted = merge_sort(items[middle_index:])

  return merge(left_sorted, right_sorted)

问题 #

这两个函数的辅助空间复杂度是否存在差异？

已知递归函数空间复杂度需计算递归执行过程中最大占用空间（通常在递归到基准情况时达到峰值，此时调用栈帧最多），公式可总结为：
$$S(n) = \sum_{i=0}^{maximum recursion depth k} S_i$$
（其中$S_i$表示第i层单个函数帧占用的空间）

对两个版本的初步分析：

• 版本1：首次递归调用前会创建两个长度为$\frac{n}{2}$的列表，初始调用占用$n$的空间；下一层递归处理$\frac{n}{2}$长度的列表，递归前创建两个$\frac{n}{4}$的列表，占用$\frac{n}{2}$空间。归并排序最大递归深度为$\log_2 n$，基准情况无新列表创建，总空间求和公式为：
  $$S(n) = \sum_{i=0}^{(log_2 n) - 1} n \times (0.5)^i$$
• 版本2：首次递归前仅创建一个$\frac{n}{2}$的列表，初始占用$\frac{n}{2}$空间；下一层递归处理$\frac{n}{2}$长度的列表，递归前创建一个$\frac{n}{4}$的列表，占用$\frac{n}{4}$空间。总空间求和公式为：
  $$S(n) = \sum_{i=0}^{(log_2 n) - 1} \frac{n}{2} \times (0.5)^i$$

已知两者大O复杂度均为$O(n)$，但想确认：版本2在首次递归后才创建第二个列表，基准情况时整体占用空间更少；版本1提前创建两个列表，每层递归占用双倍空间，任意时刻空间占用都是版本2的两倍，这种解读是否合理？

解答 #

你的解读完全合理，两者在实际运行时的峰值空间占用确实存在常数倍差异，尽管大O复杂度同为$O(n)$。

具体来说：

• 版本1在进入递归前就同时创建了左右两个拆分列表，每层递归帧都会持有这两个列表的引用，直到该层递归完成。在递归深度达到最大值时，每一层的函数帧都同时持有两个拆分后的子列表，总峰值空间是各层拆分列表长度之和，计算下来是$n + \frac{n}{2} + \frac{n}{4} + ... + 2 = 2n - 2$，近似为$2n$。
• 版本2则是先递归处理左半部分，此时仅创建左拆分列表；左半部分递归完成释放空间后，才创建右拆分列表并递归处理。在递归峰值时，同一时刻只有当前层及以下递归链的拆分列表存在，总峰值空间是$\frac{n}{2} + \frac{n}{4} + ... + 1 = n - 1$，近似为$n$。

这种差异属于常数级别的空间优化，虽然不改变大O复杂度，但在内存敏感的场景下，版本2的空间利用率确实更高。

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