Re:Linear O(N) sorting with Radix Sort (2000)
by vitorsr on Tuesday February 01, 2022 @09:34AM
(#30162909)
The following repository implements radix sorting algorithms “from the ground up” and includes some benchmarks:
Re:Linear O(N) sorting with Radix Sort (2000)
by bssrdf on Tuesday February 01, 2022 @01:31PM
(#30166963)
I implemented radix sort in cpython [0] and did some simple benchmarking comparing to python' built-in sort (Timsort I believe). It is indeed faster.
Re:Linear O(N) sorting with Radix Sort (2000)
by Ono-Sendai on Tuesday February 01, 2022 @09:12AM
(#30162615)
Here are some perf measurements I made a while ago with a serial and a parallel radix sort: https://forwardscattering.org/post/34
I'd be curious to see a deeper discussion of practical run-times, in actual seconds, relative to other popular sorting algorithms. Especially if driven by a real task with well-motivated problem constraints. (As opposed to "1000 random integers!" micro-benchmarks, or "N goes to infinity" theoretical big-Ohs.)
I personally find practical benchmarks the most exciting. They also help me identify different niches for different algos (caching, locality, array sizes, parallelization…).