在遍历 Wikipedia's list of sorting algorithms 时我注意到没有稳定的 comparison sort具有 O(n*log(n))(最坏情况)时间复杂度和 O(1)(最坏情况)空间复杂度。这看起来确实像是一个理论边界，但我找不到更多相关信息。
如何证明这一点？
注意:我知道比较排序的O(n*log(n)) 最坏情况时间复杂度的下限。
最佳答案
不管那篇文章怎么说，in-place stable Merge Sort can be made O(n log n) .
Here这篇论文解释了实现它的两种方法。
关于algorithm - 具有 O(n * log(n)) 时间复杂度和 O(1) 空间复杂度的稳定比较排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9777565/