On 04/04/2016 05:36 AM, Nordlöw wrote:
I have some C++ that does optimal sorting of 3 and 4 elements at
https://github.com/nordlow/justcxx/blob/master/sortn.hpp
Would anybody be interesting in getting this integrated into
std.algorithm.sorting
?
This is a good start but we'd need a more principled attack on the
problem. There are optimal sorting networks for a number of small sizes;
a good start is Knuth's TAoCP Volume 3 but there's newer research as
well, which needs to be investigated. A sorting network in D can be
nicely done with variadic template parameters, e.g. this:
r.conditionalSwap!(less, 0, 2, 1, 3);
expands to:
if (less(r[0], r[1])) r.swapAt(0, 2);
if (less(r[1], r[3])) r.swapAt(1, 3);
so then building a sorting network boils down to writing the right
sequence of indexes.
We'd need to figure at which point the size of the generated code
overwhelms any gains made from the specialized routines.
All of the above should be packaged in a routine:
auto sortUpTo(uint n, alias less = "a < b", Range)(Range r);
which asserts that r.length <= n, or maybe two because this is also useful:
auto sortExactly(uint n, alias less = "a < b", Range)(Range r);
which asserts that r.length == n. The documentation specifies the
largest available n.
Andrei
