Adding Radix Sort into Phobos

[Andrei Alexandrescu via Digitalmars-d]

On 4/27/15 12:52 AM, "Per =?UTF-8?B?Tm9yZGzDtnci?= 
<per.nordlow at gmail.com>" wrote:
> On Sunday, 26 April 2015 at 17:31:58 UTC, Martin Nowak wrote:
>> On 04/26/2015 09:16 AM, "Per =?UTF-8?B?Tm9yZGzDtnci?=
>> <per.nordlow at gmail.com>" wrote:
>>> I have a radix sort implementation at
>>>
>>> https://github.com/nordlow/justd/blob/master/intsort.d#L92intsort.d
>>>
>>> which beats Phobos own Quicksort by a factor 1.5 to 4 depending on
>>> element type (Intergral or FloatingPoint).
>>>
>>> Anyone up for the job of adapting and merging it into Phobos'
>>> std.algorithm.sorting?
>>
>> Code seems to be pretty done (although there are lots of TODOs).
>> Why not simply convert it into a pull request?
>
> Ok, I'll try this.
>
> Does someone have any answers to these questions or should I wait until
> the prel. pull request is done?:
>
> •Figure out a way to template-parameterize  radixSortImpl  to make it
> work on aggregate element types when the comparison function can be
> expressed as an data-member-accessor of the aggregate. For example if
> ElementType is a  struct S { int x, y; }  and comparison function "a.x <
> b.x".
> •If possible implement a generic sorting algorithm that automatically
> selects the best suitable in-Place sorting algorithm based on types of
> the input parameters (range and comparsion/accessor function). This
> currently means  isIntegral, float,  double, and as above mentioned
> aggregates sorted on a member or combination of members whose bijection
> can fit into 8, 16, 32 or 64 bits.

Yah, these are good angles/ideas. I'm curious, how come radixSort on 
long is better than quicksort? Conventional wisdom has it that quicksort 
is better for large-ish integral types. What data distributions did you 
test on? -- Andrei