Is `sort_unstable_by_key` generally faster than `sort_by_key`?

help
1

The documentation says that unstable algorithm have O(n * log(n)) complexity and doesn't allocate, as opposed to the stable algorithm with O(m * n * log(n)) complexity and allocations.

At first glace, the unstable algorithm seems better in every way, is there a catch to that? (other than the order of equal items not being preserved, which I don't care about)

1 Like
2

I'm pretty sure the sort_unstable_by_key function also has the same O(mn log n) asymptotic complexity as sort_by_key, just that the documentation is missing the m factor.

1 Like
3

So it is quite obvious that you should us sort_unstable_by_key:

From slice - Rust

in-place (i.e., does not allocate)

It is typically faster than stable sorting, except in a few special cases, e.g., when the slice is partially sorted.

But doing a benchmark test might be a good idea.

Note: The classic quicksort sorts in place, while the stable classic merge-sort used a temporary buffer, I think it was halve of the initial data size. And remember, for the classic sorting, the worst case scenario was the actual problem. For classic recursive quicksort, in worst case runtime was very bad, and could give a stack overflow.

1 Like
4

Another sidenote: the unstable sort in std is currently pattern defeating quicksort, which doesn't have an O(n^2) worst case, since it switches to heapsort (which is always O(n log n) if there were too many bad pivot element choices

2 Likes
5

The sort_unstable RFC is worth reading.

From the RFC:

Q: Is slice::sort ever faster than pdqsort?
A: Yes, there are a few cases where it is faster. For example, if the slice consists of several pre-sorted sequences concatenated one after another, then slice::sort will most probably be faster. Another case is when using costly comparison functions, e.g. when sorting strings. slice::sort optimizes the number of comparisons very well, while pdqsort optimizes for fewer writes to memory at expense of slightly larger number of comparisons. But other than that, slice::sort should be generally slower than pdqsort.

6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.