是否可以在 O(n log n) 且辅助空间不变的情况下稳定地对数组进行排序？

Question

给定一个n个元素的数组，是否有一个排序算法

1. 排序最多O(n log n)时间（并且可选地，在最好的情况下， O(n)时间）
2. 是稳定的
3. 占用O(1)辅助空间

我发现的所有排序算法仅满足以下标准中的两个：

• 冒泡排序满足2和3
• 归并排序满足1和2
• 堆排序满足1和3

有没有一种算法可以满足这三个标准？

Answer 1

来自： https: //cstheory.stackexchange.com/

存在一种稳定的就地排序算法，具有 O(n log n) 次比较和 O(n) 次移动。

请参阅：Gianni Franceschini：使用 O(n log n) 比较和 O(n) 移动进行稳定、就地排序。理论计算。系统。40(4): 327-353 (2007) 链接