为什么Rust的排序方法分配内存？

Question

像sort_by on std::slice::MutableSliceAllocating或sort_by on collections::vec::Vec这样的方法被记录为“分配大约2* n，其中n是长度”。我不认为好的C++ std::sort实现(在堆上)分配，但它们完成了相同的O(n日志n)复杂性。不过，锈蚀排序方法与C++ std::sort不同，是稳定的。

为什么锈蚀排序方法要分配？对我来说，它不符合“零成本抽象”法案的广告这里。

Answer 1

正如注释中所述，这是一个稳定的排序，它需要O(n)空间来执行。最好的O(n log n)稳定排序，合并，需要大约半个临时项目。(我对锈病并不熟悉，所以我不知道它为什么需要四倍于此。)

在O(log )空间中可以实现稳定的排序，但只能通过合并变体实现，这需要O(n Log 2 n)时间。

Answer 2

我意识到这是一篇老文章，但我在谷歌上发现，流行的答案是错误的。实际上，使用O(1) (甚至不是日志)内存和最坏的O(nlogn)时间执行稳定的就地排序是可能的。例如，参见GrailSort或WikiSort。