Open AlexTMjugador opened 2 years ago
Hello MSD radix sorts are in place but LSD sorts are out of place. The lib voracious radix sort may use one or this other depending on the situation. The subtle part is that LSD sorts can be used only up to a threshold, making the sort theoretical in place, but it would use a lot of memory. If you want to be sure to use in place sorts, you can use separately sorting MSD radix sort algorithms provided by the lib: https://docs.rs/voracious_radix_sort/1.1.0/voracious_radix_sort/#functions
In the worst case, it will use n
+ n
space
Thank you, that's useful to know! Would you look forward to a PR to mention that in the readme?
A common argument against radix sorts in general it's that they may consume more memory than other sorting algorithms. The documentation of the
voracious_sort
function explicitly states that it is an in-place algorithm, suggesting that its space complexity is either constant or at mostlog n
, but the benchmarks do no memory usage comparison between the different sorting algorithms.Given that not everyone has gigabytes of RAM to throw at the problem of sorting big arrays, I think it'd be pretty interesting to consider how it fares in memory usage too. Being very fast might does not matter when swapping memory anyway, and people finding that out the hard way is not ideal.