Another algo for faster sorting

[Andrei Alexandrescu via Digitalmars-d]

On 4/8/16 6:06 AM, Andrea Fontana wrote:
> On Friday, 8 April 2016 at 07:33:32 UTC, deadalnix wrote:
>> On Thursday, 7 April 2016 at 13:32:43 UTC, Andrea Fontana wrote:
>>> On Thursday, 7 April 2016 at 10:58:21 UTC, Dmitry Olshansky wrote:
>>>> Coincidentally with another NG thread I'm curious if we can
>>>> special-case our sort for
>>>> strings to Three-Way Radix QuickSort which is more efficient:
>>>>
>>>> http://www.drdobbs.com/database/sorting-strings-with-three-way-radix-qui/184410724
>>>>
>>>
>>> Radix sort is a very fast way to sort strings and integers . But it
>>> does not work with a custom " less" function . It just sorts date to
>>> lexical way .
>>>
>>
>> You can make it work with float as well with some horrible hacks. I
>> tried to implement it, but performances were not that great at the
>> end. Maybe I missed something, or maybe this is just not CPU friendly
>> enough for the sample I had to throw at it.
>>
>> See: https://github.com/deadalnix/Dsort/blob/master/sort/radix.d
>
> Using your functions to radixify float this seems to run faster for me
> than phobos sort (for large arrays 2x, 3x it seems... not so many
> benchmarks)
>
> http://dpaste.dzfl.pl/1b4752ff37b1
>
> I don't optimize it that much. Just did a try.
>
> Andrea

Guess we need a pull request. In order to distinguish the "less than" 
(default) predicate from arbitrary predicates, just define two overloads 
of sort, one without the predicate parameter. -- Andrei