On 22 July 2013 00:58, Steven Ross
It is MSD radix sort, which is recursive bucket sort, combined with switching to std::sort once the problem is cut up small enough that std::sort has better worst-case performance. Conventional MSD radix sorts use insertion sort for small problems instead, and switch at much smaller data sizes, which can be problematic for performance with data that is unevenly distributed (conventional MSD radix sorts take about 4X as long as std::sort in this case).
Ah, I apologize for the misunderstanding and thank you for clearing it up.
Reverse sorting could be done by passing reverse iterators, though that
eliminates the possibility of using raw pointers, which are slightly faster
with some of the compilers I tested. I'd be happy to remove the reverse calls if there is general agreement that the performance difference isn't a problem.
If performance is the only reason can you provide or link to some empirical data? Presumably the same decision must have been broached with regard to std::sort() and there is no std::reverse_sort(). This discussion on SO suggests that with enough optimization all iterators are equal: http://stackoverflow.com/questions/9025084/sorting-a-vector-in-descending-or... It also points out that reverse sorting can be achieved with forward iterators by using the opposite sorting functor. An LSD radix sort could make sense as an additional option, and counting
sort would make sense as a part of that. LSD is substantially different
from MSD radix sort, so it seems like a separate project to me. LSD radix sort is often slower than std::sort on real problems because it can't take advantage of easy problems. It also uses more memory. and doesn't make sense on variable-length data types. All that said, it is useful for some types of problems, such as when stability is a requirement.
I certainly haven't done extensive testing, but so far the stable counting-sort has been much quicker than std::sort(). It has even been quicker than your code for small (< 1000) values of k (maximum value). :) The non-stable counting-sort (based on Rosetta Code) is faster still, so I'm curious to see some extensive performance tests. My LSD radix-sort is almost finished, I'll let you know when. Cheers. Jeremy