Re: [boost] radix sort

Subject: Re: [boost] radix sort
From: Steven Ross (spreadsort_at_[hidden])
Date: 2013-07-25 06:15:59

On Tue, Jul 23, 2013 at 11:19 AM, Jeremy Murphy <
jeremy.william.murphy_at_[hidden]> 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.