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, AndreiDone.
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