Fixed-Length Array Sorting

[Andrei Alexandrescu via Digitalmars-d]

On 04/13/2016 12:07 PM, Nordlöw wrote:
> On Tuesday, 12 April 2016 at 14:56:00 UTC, Andrei Alexandrescu wrote:
>> Also to avoid cache line thrashing, sort parallel swaps by leftmost
>> index. E.g. this line:
>>
>> 18,19, 20,21, 2,4, 1,3, 0,5, 6,8, 7,9, 10,12, 11,13,
>>
>> becomes:
>>
>> 0,5, 1,3, 2,4, 6,8, 7,9, 10,12, 11,13, 18,19, 20,21,
>>
>>
>> Andrei
>
> Done.

No time but couple more remarks:\

* Cut and paste error at 
https://github.com/nordlow/phobos-next/blob/master/src/sortn.d#L90

* I see some sizes are not supported, we should not have holes.

* Sometimes the sort routine gets too bulky. Suggestion: also define 
networks for medianOfUpTo and medianExactly, then use them in a 
quicksort manner - first compute the median to segregate values in 
below/over the median, then make two calls to sortExactly!(n / 2). That 
way you get to sort n values with median of n values (smaller and 
simpler) and two sorts of n / 2 values.

I think this is great work in the making. We should be able at some 
point to plug this into std.sort.


Andrei