3 ms·
Rust's stable sort is based on timsort (https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort https://doc.rust-lang.org/std/vec/struct.Vec.html#method.s
by atilimcetin 9y ago
Rust's stable sort is based on timsort (https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sort 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.sort_unstable 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.'
- k__ 9y agohow much faster?
- sgift 9y agoHere are a few benchmarks results from a recent rayon pull: https://github.com/nikomatsakis/rayon/pull/379 https://github.com/nikomatsakis/rayon/pull/379 So, for a dual-core with HT 8.26s vs 4.55s
- gnarbarian 9y agoI 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).
- partycoder 9y agoJust that it takes extra space and that's sometimes a constraint.
- chii 9y agohttps://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm https://stackoverflow.com/questions/2571049/how-to-sort-in-p... In place merge sort exists. It's hard to write tho
- tomlx 9y agoThis is beautiful. I will try to implement this once i'm at home ...
- partycoder 9y agoWhich decreases the space complexity but increases the time complexity.
- stjepang 9y agoNo, 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-algorithms.pdf https://sites.google.com/site/algoxy/home/elementary-algorit...
- EvgeniyZh 9y ago...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