blitsort
crumsort
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.
blitsort
- Glidesort, a new stable sort in Rust up to ~4x faster for random data
- GitHub - scandum/blitsort: Blitsort is an in-place stable adaptive rotate mergesort / quicksort (Not C#)
-
Hacker News top posts: Dec 2, 2022
Blitsort: A fast, in-place stable hybrid merge/quick sort\ (62 comments)
- Blitsort: A fast, in-place stable hybrid merge/quick sort
-
Blitsort: An ultra-fast in-place stable hybrid merge/quick sort
Looks like the author added the `LICENSE` file in repo root after this comment: https://github.com/scandum/blitsort/blob/main/LICENSE
This is always a great point to bring up, though. People who don't properly declare the license of their OSS projects are (either unintentionally or internionally) make it a headache for companies to use. I'm not saying it's bad to explicitly deny corporate use (via GPL, etc.). The real problem IMO is when other OSS projects vendor unlicensed code and then declare their projects to be under MIT license. Then if a corporation uses it, they're unknowingly violating the copyright of the transitive dep.
- Blitsort: An in-place stable sorting algorithm faster than qsort and pdqsort
- Blitsort: An in-place stable sorting algorithm faster than pdqsort
- I tried creating a sorting algorithm in C language.
- Blitsort is an in-place stable adaptive rotate merge sort
crumsort
-
Blitsort: An ultra-fast in-place stable hybrid merge/quick sort
Blitsort is a hybrid quicksort, see title.
It is slower than it's unstable brother, aptly named crumsort. https://github.com/scandum/crumsort
- Crumsort: Introduction to a new unstable sorting algorithm faster than pdqsort
- 380 points in 6 hours
- Crumsort: Introduction to a new sorting algorithm faster than pdqsort
-
Go will use pdqsort in the next release
https://github.com/scandum/crumsort claims better performance than pdqsort
-
Changing std:sort at Google’s Scale and Beyond
Any chance you could comment on fluxsort[0], another fast quicksort? It's stable and uses a buffer about the size of the original array, which sounds like it puts it in a similar category as glidesort. Benchmarks against pdqsort at the end of that README; I can verify that it's faster on random data by 30% or so, and the stable partitioning should mean it's at least as adaptive (but the current implementation uses an initial analysis pass followed by adaptive mergesort rather than optimistic insertion sort to deal with nearly-sorted data, which IMO is fragile). There's an in-place effort called crumsort along similar lines, but it's not stable.
I've been doing a lot of work on sorting[2], in particular working to hybridize various approaches better. Very much looking forward to seeing how glidesort works.
[0] https://github.com/scandum/fluxsort
[1] https://github.com/scandum/crumsort
[2] https://mlochbaum.github.io/BQN/implementation/primitive/sor...
What are some alternatives?
quadsort - Quadsort is a branchless stable adaptive mergesort faster than quicksort.
fluxsort - A fast branchless stable quicksort / mergesort hybrid that is highly adaptive.
pdqsort - Pattern-defeating quicksort.
awesome-algorithms - A curated list of awesome places to learn and/or practice algorithms.
SHOGUN - Shōgun
gridsort - A stable adaptive partitioning comparison sort.
awesome-theoretical-computer
tremc - Curses interface for transmission
awesome-theoretical-computer-science - The interdicplinary of Mathematics and Computer Science, Distinguisehed by its emphasis on mathemtical technique and rigour.
highway - Performance-portable, length-agnostic SIMD with runtime dispatch
combsort.h - optimized combsort macro