algorithm - 无需额外空间或就地合并排序

Question

可能重复：
如何使用归并排序算法就地排序？

通常我们需要一个额外的数组来使用归并排序对其进行排序，是否可以在不使用额外空间的情况下做到这一点？

如果这是可能的，那么合并排序会比快速排序更好吗？

Answer 1

是的，可以执行就地合并排序。这并不意味着它不需要任何额外的内存，因为递归仍然需要 O(lg n ) 堆栈空间（就像快速排序一样）。

编辑：我已经很久没有阅读 Katajainen 的论文了，而且我从来没有关注过空间复杂度的说法；显然，合并排序可以在 O(1) 额外空间中完成。

但是，不，这并不意味着一种算法比另一种更好，除非您指定该词的含义。随机快速排序虽然可以进行二次排序，但无论输入如何，它仍然执行较少的预期操作。哪一个对您的数据“效果更好”取决于从数据统计到程序运行的硬件等因素。