On Tue, Jul 23, 2013 at 11:19 AM, Jeremy Murphy < jeremy.william.murphy@gmail.com> wrote:
In terms of performance, it performs poorly on 64-bit integers, competitively on 32-bit integers, and quite impressively on 16-bit and 8-bit integers.
Yes, radix sorts work great when the data type is small (such as 8-bit or 16-bit integers). To get a better comparison against std::sort for the larger integers, I suggest you use data in a range roughly matching the size of the data type (what is RAND_MAX on your system? It's usually less than 1 << 16). As a note, MSD radix sort is extremely fast on the evenly-distributed random data that it looks like you're using. I test Spreadsort with a bunch of uneven distributions that make the problem harder, in addition to a few tests with evenly distributed random data. LSD radix sort doesn't care much about distribution, but most other algorithms (including std::sort) do.