While the main conclusion of the article isn't unexpected to me I am very surprised a well optimized quicksort isn't faster than radix sort.
My experience in C is that you can significantly speed-up quick sort by removing function calls and doing insertion sorts on small arrays at the end. I was never able to get radix sort even close to that performance wise.
I don't know Rust at all so it would be pointless for me to try to code an optimized quick sort in it. Hopefully the author knows how to optimize quick sort and is not missing on huge gains there.
Just in case someone feels like porting it to Rust, here is a link to a good and simple quick sort implementation that significantly outperforms standard library one:
https://www.ucw.cz/libucw/doc/ucw/sort.html
> it would be pointless for me to try to code an optimized quick sort in it.
Perhaps more so than you've realised. Hint: Rust's old unstable sort was its take on the pattern defeating quicksort. The article is talking about the new unstable sort which has better performance for most inputs.
Rust uses monomorphization and its function types are unique, so the trick you're used to with a macro is just how everything works all the time in Rust.
The trick is not about macros but about removing function calls altogether.
Macros are there only to generate functions for specific types.
The way the trick works is to implement the stack manually and put indexes there instead of passing them as function arguments. This removes a lot of overhead and makes the implementation I linked to significantly faster than C's and C++'s standard library implementation.
It's not my imagination. It's my experience with benchmarking it.
The implementation I linked to is 2x (or even more on relatively short arrays) faster than standard library C++ sort. Is Rust sort as fast?
Just in case someone feels like porting it to Rust, here is a link to a good and simple quick sort implementation that significantly outperforms standard library one: https://www.ucw.cz/libucw/doc/ucw/sort.html