On 4/27/15 12:52 AM, "Per =?UTF-8?B?Tm9yZGzDtnci?=
<[email protected]>" 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?=
<[email protected]>" 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
