Flo*_*ker 6 sorting algorithm complexity-theory proof
在浏览维基百科的排序算法列表时,我注意到没有稳定的比较排序具有O(n*log(n))(最坏情况)时间复杂度和O(1)(最坏情况)空间复杂度.这肯定看起来像理论界限,但我找不到更多关于它的信息.
如何证明这一点？
注意:我知道O(n*log(n))比较排序的最坏情况时间复杂度的下限.
尽管那篇文章说的是,可以制作就地稳定的Merge SortO(n log n).
这是一篇论文,解释了实现它的两种方法.