algorithm - 稳定、高效的排序？

Question

我正在尝试创建一个非常节省空间的不寻常的关联数组实现，我需要一个满足以下所有条件的排序算法:

1. 稳定(不改变具有等键的元素的相对顺序。)
2. 就地或几乎就地(O(log n) 堆栈很好，但没有 O(n) 空间使用或堆分配。
3. O(n log n) 时间复杂度。

另请注意，待排序的数据结构是一个数组。

很容易看出有一个基本算法可以匹配这三个中的任意两个(插入排序匹配 1 和 2，归并排序匹配 1 和 3，堆排序匹配 2 和 3)，但我一辈子都做不到找到符合所有这三个条件的任何内容。

Answer 1

我相信合并排序可以写成就地。这可能是最好的路线。