[atilimcetin]

Rust's stable sort is based on timsort (https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...) and unstable sort is based on pattern-defeating quicksort (https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...). The documentation says that 'It [unstable sorting] is generally faster than stable sorting, except in a few special cases, e.g. when the slice consists of several concatenated sorted sequences.'

[gnarbarian]

I like merge sort. Average time may be worse, but it's upper bound is better and it is conceptually cleaner and easier to understand (IMO).

[badminton1]

Just that it takes extra space and that's sometimes a constraint.

[chii]

https://stackoverflow.com/questions/2571049/how-to-sort-in-p...

In place merge sort exists. It's hard to write tho

[badminton1]

Which decreases the space complexity but increases the time complexity.

[_hrfd]

No, the time complexity is the same: O(n log n). The author of the top answer links to his book, where you can find a proof of time complexity:

https://sites.google.com/site/algoxy/home/elementary-algorit...

[EvgeniyZh]

...but it increases run time. It's fine not to care on hidden constants while analyzing algorithms, but not while using them in real life

[tomlx]

This is beautiful. I will try to implement this once i'm at home ...

[k__]

how much faster?

[sgift]

Here are a few benchmarks results from a recent rayon pull:

https://github.com/nikomatsakis/rayon/pull/379

So, for a dual-core with HT 8.26s vs 4.55s