CODEWITHSUNDEEP
sortingrustdynamic-allocation
kmky
kmky

Reputation: 801

Why do Rust's sort methods allocate memory?

Methods like sort_by on std::slice::MutableSliceAllocating or sort_by on collections::vec::Vec are documented to "allocate approximately 2 * n, where n is the length". I don't think that good C++ std::sort implementations allocate (on the heap) and yet they accomplish the same O(n log n) complexity. Although, the Rust sort methods are stable unlike the C++ std::sort.

Why do the Rust sort methods allocate? To me, it doesn't fit the "zero cost abstraction" bill advertised here.

Upvotes: 2

Views: 1259

Answers (2)

terpstra
terpstra

Reputation: 153

I realise this is an old post, but I found it on google and the popular answer is wrong. It is in fact possible to perform a stable in-place sort using O(1) (not even log) memory and worst-case O(nlogn) time. See for example GrailSort or WikiSort.

Upvotes: 8

Fred Foo
Fred Foo

Reputation: 363767

As stated in the comment, this is a stable sort, which requires O(n) space to execute. The best O(n log n) stable sort, mergesort, requires about ½n temporary items. (I'm not familiar with Rust, so I don't know why it needs four times that.)

Stable sort can be achieved in O(log n) space, but only by mergesort variant that takes O(n log² n) time.

Upvotes: 7

Related Questions