MergeSortの時間計算量は基本的な知識であるO（nlgn）です。マージソートスペースの複雑さは、配列を含めて常にO（n）になります。スペースツリーを描くと、スペースの複雑さはO（nlgn）のように見えます。ただし、コードは深さ優先コードであるため、常にツリーの1つのブランチに沿って拡張するだけです。したがって、必要な合計スペース使用量は常に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;
}
これがお役に立てば幸いです！=）
すぐにチーロン、
トロント大学