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