在学习合并排序算法时，我很想知道这种排序算法是否可以进一步优化。发现存在迭代版本的Merge-Sort算法，该算法具有相同的时间复杂度，但具有更好的O(1)空间复杂度。迭代方法在性能上总是优于递归方法。那么，为什么它在任何常规的算法课程中都不那么常见，也很少被谈论呢？这是迭代合并排序算法的链接
如果您认为它具有O(1)空间复杂性，请再次查看。它们具有大小为n的原始阵列A和大小也为n的辅助temp。(实际上它只需要是n/2，但他们保持了简单。(
他们需要第二个数组的原因是，当合并时，将底部区域复制到temp，然后从原来的位置合并回来。
因此，权衡是这样的。递归解决方案涉及更少的麻烦位，使概念更清晰，但在两种解决方案共享的O(n)内存开销之上添加了O(log(n))内存开销。当你试图交流概念时，这是一场直接的胜利。
此外，在实践中，我相信递归也是一种胜利。
在迭代方法中，您可以在整个数组中进行完整的传递。在大型数组的情况下，这意味着数据进入缓存进行传递，然后被操纵，然后在加载数组的其余部分时脱落。只需要在下一次通过时再次加载。
相比之下，在递归方法中，对于相当于前几次通过的操作，你将它们加载到缓存中，完全排序，然后继续。算法课程通常会省略这些低级细节，但它们对现实世界的性能非常重要。
发现存在迭代版本的合并排序算法，该算法具有相同的时间复杂度，但具有更好的O(1(空间复杂度
您链接到的Merge Sort的迭代、自下而上的实现不具有O(1(空间复杂性。它维护数组的副本，因此这表示O(n(空间复杂性。因此，这使得额外的O(logn(堆栈空间(对于递归实现(与总空间复杂性无关。
在你的问题标题和一些评论中，你使用了"辅助空间复杂性">。这就是我们通常所说的空间复杂性，但你似乎认为这个术语的意思是常数空间复杂性。这不是真的"辅助"；是指输入使用的空间之外的空间。这个术语告诉我们实际的复杂性。
递归自上而下的合并排序主要是教育性的。大多数实际库使用混合插入排序和自下而上合并排序的一些变体，使用插入排序创建小的排序运行，这些运行将在偶数次合并过程中合并，因此，在原始数组和临时数组之间来回合并最终会得到原始数组中已排序的数据(除了在数组末尾运行singleton之外，合并中没有复制操作，这可以通过为插入排序选择适当的初始运行大小来避免(注意，在我的示例代码中没有这样做，我只使用32或64的运行大小，而像Timsort这样更高级的方法确实选择了合适的运行大小(。
自下而上的速度稍快，因为数组指针和索引将保留在寄存器中(假设是优化编译器(，而自上而下的是从堆栈中向|弹出数组指针和指数。
虽然我不确定OP是否真的意味着合并排序的O(1(空间复杂性，但这是可能的，但它比具有O(n(辅助空间的传统合并排序慢大约50%。现在这主要是一项研究(教育(工作。代码相当复杂。链接到示例代码。其中一个选项是根本没有额外的缓冲区。基准表用于数量相对较少的键(最大为32767个键(。对于大量的键，这个例子最终比优化的插入+自下而上的合并排序慢大约50%(std:：stable_sort是广义的，比如每次比较都使用指向函数的指针，所以它没有完全优化(。
https://github.com/Mrrl/GrailSort
示例混合插入+自下而上合并排序C++代码(省略原型(：
void MergeSort(int a[], size_t n) // entry function
{
if(n < 2) // if size < 2 return
return;
int *b = new int[n];
MergeSort(a, b, n);
delete[] b;
}
void MergeSort(int a[], int b[], size_t n)
{
size_t s; // run size
s = ((GetPassCount(n) & 1) != 0) ? 32 : 64;
{ // insertion sort
size_t l, r;
size_t i, j;
int t;
for (l = 0; l < n; l = r) {
r = l + s;
if (r > n)r = n;
l--;
for (j = l + 2; j < r; j++) {
t = a[j];
i = j-1;
while(i != l && a[i] > t){
a[i+1] = a[i];
i--;
}
a[i+1] = t;
}
}
}
while(s < n){ // while not done
size_t ee = 0; // reset end index
size_t ll;
size_t rr;
while(ee < n){ // merge pairs of runs
ll = ee; // ll = start of left run
rr = ll+s; // rr = start of right run
if(rr >= n){ // if only left run
rr = n; // copy left run
while(ll < rr){
b[ll] = a[ll];
ll++;
}
break; // end of pass
}
ee = rr+s; // ee = end of right run
if(ee > n)
ee = n;
Merge(a, b, ll, rr, ee);
}
std::swap(a, b); // swap a and b
s <<= 1; // double the run size
}
}
void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
size_t o = ll; // b[] index
size_t l = ll; // a[] left index
size_t r = rr; // a[] right index
while(1){ // merge data
if(a[l] <= a[r]){ // if a[l] <= a[r]
b[o++] = a[l++]; // copy a[l]
if(l < rr) // if not end of left run
continue; // continue (back to while)
while(r < ee) // else copy rest of right run
b[o++] = a[r++];
break; // and return
} else { // else a[l] > a[r]
b[o++] = a[r++]; // copy a[r]
if(r < ee) // if not end of right run
continue; // continue (back to while)
while(l < rr) // else copy rest of left run
b[o++] = a[l++];
break; // and return
}
}
}
size_t GetPassCount(size_t n) // return # passes
{
size_t i = 0;
for(size_t s = 1; s < n; s <<= 1)
i += 1;
return(i);
}