Franceschini方法如何运作？

Question

在维基百科上提到,此方法在O(n log n)时间内对数组进行排序,但它也是稳定且就地的.这听起来像是一个非常好的排序算法,因为没有其他排序算法一次完成所有这些(Insertion Sort不是O(n log n),Heap Sort不稳定,Quicksort(或Introsort)也不是放置或稳定,Mergesort不在位).但是,在维基百科上只提到了它的名字而没有别的.作为参考,它是Franceschini,Gianni(2007年6月1日)."使用O(n log n)比较和O(n)移动稳定地进行排序".计算系统理论40(4):327-353.然而,这并没有真正解释它是如何实际运作的,它更多地说明了它存在的原因.

我的问题是这个方法是如何工作的(它实际上做了什么步骤),以及为什么有这么少的资源与它有关,考虑到没有其他已知的O(n log n)稳定到位的排序方法.

Answer 1

\n

考虑到没有其他已知的 O(n log n) 稳定的就地排序方法。

\n

\n\n

使用O(log n)额外空间就地实现合并排序非常容易，我想这在实践中已经足够接近了。

\n\n

事实上，有一种稳定的合并排序变体，仅使用O(1)额外内存：Katajainen、Pasanen 和 Teuhola 的“实用就地合并排序”。它具有最佳的O(n log n)运行时间，但它并不是最佳的，因为它使用\xce\xa9(n log n)元素移动操作，而正如 Franceschini 论文所演示的那样，它可以使用O(n)来完成。

\n\n

它的运行速度似乎比传统的合并排序慢，但幅度也不是很大。相比之下，Franceschini 版本似乎要复杂得多，并且有巨大的恒定开销。

\n