Fixed-Length Array Sorting
Andrei Alexandrescu via Digitalmars-d
digitalmars-d at puremagic.com
Thu Apr 7 06:09:22 PDT 2016
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
More information about the Digitalmars-d
mailing list