归并排序时间复杂度是O(nlgn)，这是一个基础知识。
归并排序空间复杂度始终为 O(n)，包括数组。
如果你把空间树画出来，看起来空间复杂度是O(nlgn)。然而，由于代码是深度优先代码，您将始终仅沿着树的一个分支进行扩展，因此，所需的总空间使用量始终受 O(3n) = O(n) 的限制。
2023 年 10 月 24 日更新：有一个问题是关于我如何得出 3n 上限的。
我在评论中的解释并重新粘贴在这里。 3n 的数学证明与为什么从未排序数组构建堆的时间复杂度上限为 2n 次交换的时间复杂度非常相似，这需要 O(2n) = O(n) 时间。在这种情况下，始终只有 1 个额外分支。因此，可以将其视为为 1 个附加分支再次执行 buildHeap。因此，它将受到另一个 n 的限制，总上限为 3n，即 O(3n) = O(n)。请注意，在本例中，我们使用 buildHeap(inputArray) 时间复杂度中的类似数学来证明单线程归并排序的空间复杂度，而不是时间复杂度。当我有时间的时候，我可以为此写出完整的严格的数学证明。
- 构建堆的时间复杂度怎么可能是O(n)？ https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity
比如说，如果你把空间树画出来，看起来是O(nlgn)
16 | 16
/ \
/ \
/ \
/ \
8 8 | 16
/ \ / \
/ \ / \
4 4 4 4 | 16
/ \ / \ / \ / \
2 2 2 2..................... | 16
/ \ /\ ........................
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 | 16
其中树的高度为 O(logn) => 空间复杂度为 O(nlogn + n) = O(nlogn)。
然而，实际代码并非如此，因为它不是并行执行的。例如，在 N = 16 的情况下，这就是归并排序代码的执行方式。 N = 16。
16
/
8
/
4
/
2
/ \
1 1
注意使用的空间数量是 32 = 2n = 2*16
然后向上合并
16
/
8
/
4
/ \
2 2
/ \
1 1
即 34
16
/
8
/ \
4 4
/
2
/ \
1 1
36
然后向上合并
16
/ \
8 8
/ \
4 4
/ \
2 2
/\
1 1
16 + 16 + 14 = 46
在更大的情况下，n = 64
64
/ \
32 32
/ \
16 16
/ \
8 8
/ \
4 4
/ \
2 2
/\
1 1
这是 643 n = 3*64
您可以通过一般情况的归纳来证明这一点。
因此，即使使用数组实现，只要在合并后清理已用空间并且不是并行而是顺序执行代码，空间复杂度始终受 O(3n) = O(n) 限制。
我的实现示例如下：
templace<class X>
void mergesort(X a[], int n) // X is a type using templates
{
if (n==1)
{
return;
}
int q, p;
q = n/2;
p = n/2;
//if(n % 2 == 1) p++; // increment by 1
if(n & 0x1) p++; // increment by 1
// note: doing and operator is much faster in hardware than calculating the mod (%)
X b[q];
int i = 0;
for (i = 0; i < q; i++)
{
b[i] = a[i];
}
mergesort(b, i);
// do mergesort here to save space
// http://stackoverflow.com/questions/10342890/merge-sort-time-and-space-complexity/28641693#28641693
// After returning from previous mergesort only do you create the next array.
X c[p];
int k = 0;
for (int j = q; j < n; j++)
{
c[k] = a[j];
k++;
}
mergesort(c, k);
int r, s, t;
t = 0; r = 0; s = 0;
while( (r!= q) && (s != p))
{
if (b[r] <= c[s])
{
a[t] = b[r];
r++;
}
else
{
a[t] = c[s];
s++;
}
t++;
}
if (r==q)
{
while(s!=p)
{
a[t] = c[s];
s++;
t++;
}
}
else
{
while(r != q)
{
a[t] = b[r];
r++;
t++;
}
}
return;
}
