mountain-sort
The best algorithm to sort mountains (by Morwenn)
Presentations
Collection of personal presentations (by Voultapher)
mountain-sort | Presentations | |
---|---|---|
1 | 1 | |
3 | 7 | |
- | - | |
10.0 | 10.0 | |
over 8 years ago | over 1 year ago | |
C++ | C++ | |
MIT License | Apache License 2.0 |
The number of mentions indicates the total number of mentions that we've tracked plus the number of user suggested alternatives.
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
mountain-sort
Posts with mentions or reviews of mountain-sort.
We have used some of these posts to build our list of alternatives
and similar projects. The last one was on 2023-06-10.
-
10~17x faster than what? A performance analysis of Intel x86-SIMD-sort (AVX-512)
It depends on the size of the structs. For struct pointers you're likely better off sorting keys and pointers simultaneously. It doesn't matter much until you get to large sizes (millions), but sorting indices and then selecting with them is random access. If the original ordering is messy, selecting can be slower than the sorting step. For structs a few words long, the unit you're moving is a larger portion of a cache line, and I'd expect the data movement to drown out any SIMD advantage. A radix sort might be all right because it moves less, but I'd probably go with sorting indices as the first thing to try unless I knew the arrays were huge. For very large structs there's an interesting effort called mountain sort[0], "probably the best sorting algorithm if you need to sort actual mountains by height". Given that it minimizes number of moves it's ignoring cache entirely. I haven't benchmarked so I can't say much about how practical it is.
[0] https://github.com/Morwenn/mountain-sort
Presentations
Posts with mentions or reviews of Presentations.
We have used some of these posts to build our list of alternatives
and similar projects. The last one was on 2023-06-10.
-
10~17x faster than what? A performance analysis of Intel x86-SIMD-sort (AVX-512)
If you look at the history of the author's own sorting implementation (ipnsort), it started as an attempt to port fluxsort to Rust:
https://github.com/Voultapher/Presentations/blob/master/rust...
It starts there, eventually the author abandons the linked PR because of a better approach found with ipnsort:
https://github.com/rust-lang/rust/pull/100856#issuecomment-1...
What are some alternatives?
When comparing mountain-sort and Presentations you can also consider the following projects:
rotate - A collection of array rotation algorithms.
sort-research-rs - Test and benchmark suite for sort implementations.
quadsort - Quadsort is a branchless stable adaptive mergesort faster than quicksort.
rust - Empowering everyone to build reliable and efficient software.
highway - Performance-portable, length-agnostic SIMD with runtime dispatch
fluxsort - A fast branchless stable quicksort / mergesort hybrid that is highly adaptive.