sorting - 是否可以在具有恒定辅助空间的 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) http://www.springerlink.com/content/d7348168624070v7/