我正在尝试了解合并排序O（n）的空间要求。
我看到时间要求基本上是水平（logn）* merge（n）的数量，因此等于（n log n）。
现在，我们仍在每个级别中，在左右两个2个不同的数组中分配n。
我确实知道，这里的关键是当递归函数返回时，空间将被释放，但是我认为它并不明显。
此外，我发现的所有信息仅说明所需的空间为O（n），但不作说明。
有什么提示吗？

function merge_sort(m)
    if length(m) ≤ 1
        return m
    var list left, right, result
    var integer middle = length(m) / 2
    for each x in m up to middle
         add x to left
    for each x in m after middle
         add x to right
    left = merge_sort(left)
    right = merge_sort(right)
    result = merge(left, right)
    return result

编辑 好的，感谢@Uri，这是窍门
我一开始没看到的是时间只增加，而内存增加和减少，所以最大时间是在执行结束时，但是最大时间是内存位于递归堆栈的底部。

因此，如果我们不断添加n + n / 2 + n / 4 + n /
8…。无论添加多少次，它都不会大于2n，并且当我们到达递归堆栈时从下到上开始，我们不保留用于前一个分支的内存，因此在最大内存为2n的情况下将使用O（n）。