带O稳定的比较排序(N *的log(n))时间和O(1)空间复杂度

带O稳定的比较排序(N *的log(n))时间和O(1)空间复杂度

问题描述:

尽管经历Wikipedia's的我注意到,有没有稳定的比较排序排序算法的名单,有 O(N *的log(n))(最坏情况下)的时间复杂度和 O(1)(最坏情况)的空间-复杂。这当然看起来像一个理论上的边界,但我无法找到关于它的更多信息。

While going through Wikipedia's list of sorting algorithms I noticed that there's no stable comparison sort that has O(n*log(n)) (worst-case) time-complexity and O(1) (worst-case) space-complexity. This surely looks like a theoretical boundary, but I couldn't find more information about it.

将如何证明这一点?

注:我知道的下限为O(n *的log(n))最坏情况下的时间复杂度进行比较排序

Note: I know about the lower limit of O(n*log(n)) worst-case time-complexity for comparison sorts.

尽管这是什么文章说,在, -place稳定合并排序可为O(n log n)的

Despite what that article says, in-place stable Merge Sort can be made O(n log n).

Here是一份文件,说明了两种方法来实现它的方式。

Here is a paper that explains two ways to implement it.