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/

There exists a stable in-place sorting algorithm with O(n log n)comparisons and O(n) moves.

See: Gianni Franceschini: Sorting Stably, in Place, with O(n log n)Comparisons and O(n) Moves. Theory Comput. Syst. 40(4): 327-353 (2007)Link