在研究归并排序算法时，我很好奇这个排序算法是否可以进一步优化。发现存在迭代版本的归并排序算法，其时间复杂度相同，但空间复杂度更好O(1)。就性能而言，迭代方法总是优于递归方法。那么为什么它在任何常规算法类(class)中都不那么常见并且很少被谈论呢？
Here's the link to Iterative Merge Sort algorithm
最佳答案
如果您认为它具有 O(1) 空间复杂度，请再看一遍。它们具有大小为 n 的原始数组 A，以及大小同样为 n 的辅助 temp。 (实际上只需要 n/2 但他们保持简单。)
他们需要第二个数组的原因是，当您合并时，您将底部区域复制到临时区域，然后从原来的位置开始合并回来。
所以权衡是这样的。递归解决方案涉及更少的繁琐位，并使概念更清晰，但会在 O(n) 内存之上添加 O(log(n)) 内存开销两种解决方案共享的开销。当您尝试交流概念时，这是一个直接的胜利。
此外，在实践中我相信递归也是一种胜利。
在迭代方法中，您不断地完整遍历整个数组。在大型数组的情况下，这意味着数据会进入缓存并进行操作，然后在加载数组的其余部分时丢失。只是必须在下一次传递时再次加载。
相比之下，在递归方法中，对于相当于前几遍的操作，您将它们加载到缓存中，对它们进行完全排序，然后继续。 (您获得此胜利的次数在很大程度上取决于数据类型、内存布局和 CPU 缓存的大小。)只有当您合并太多数据以适应缓存时，您才从缓存加载/卸载。算法类(class)通常会忽略此类低级细节，但它们对现实世界的性能非常重要。
关于algorithm - 为什么递归归并排序优于迭代归并排序，即使后者具有辅助空间复杂性？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/66695718/