MergeSort 时间复杂度是 O(nlgn)，这是一个基础知识。合并排序空间复杂度将始终为 O(n)，包括数组。如果你把空间树画出来，看起来空间复杂度是 O(nlgn)。但是，由于代码是深度优先代码，您将始终只沿着树的一个分支扩展，因此，所需的总空间使用将始终以 O(3n) = O(n) 为界。
比如把空间树画出来，好像是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 < 3n
然后向上合并
16
/
8
/
4
/ \
2 2
/ \
1 1
这是 34 < 3n。然后向上合并
16
/
8
/ \
4 4
/
2
/ \
1 1
36 < 16 * 3 = 48
然后它向上合并
16
/ \
8 8
/ \
4 4
/ \
2 2
/\
1 1
16 + 16 + 14 = 46 < 3*n = 48
在更大的情况下，n = 64
64
/ \
32 32
/ \
16 16
/ \
8 8
/ \
4 4
/ \
2 2
/\
1 1
这是 64*3 <= 3*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;
}
希望这会有所帮助！=）
顺志龙，
多伦多大学