在不使用其他数组的情况下实现mergesort？

Question

我最近阅读了很多有关mergesort的文章，我想知道是否有一种方法可以在不使用至少一个其他数组的情况下进行mergesort。可能吗？

Answer 1

根据维基百科，这确实是可能的，但可能不会产生任何性能提升：

就地排序是可能的（例如，使用列表而不是数组），但非常复杂，并且在实践中几乎不会带来性能提升，即使算法运行时间为 O( n log n ) 。在这些情况下，像堆排序这样的算法通常可以提供相当的速度，并且复杂程度要低得多。此外，与标准合并排序不同，就地合并排序不是稳定的排序。在链表的情况下，算法不会使用比列表表示已经使用的空间更多的空间，而是用于递归跟踪的O(log( k )) 。有些人会认为对链表进行排序并不到位，因为即使您在给定的数据结构中进行排序，该数据结构本质上也具有您正在操作的 O( n ) 额外数据（例如，列表中的链接）。