Fixed-Length Array Sorting

[Andrei Alexandrescu via Digitalmars-d]

On 04/12/2016 06:49 AM, Nordlöw wrote:
> On Thursday, 7 April 2016 at 13:09:22 UTC, Andrei Alexandrescu wrote:
>> This is a good start but we'd need a more principled attack on the
>> problem.
>
> Ok, Andrei! Here's a start.
>
> https://github.com/nordlow/phobos-next/blob/master/src/sortn.d
>
> Currently uses Phobos' permutations for complete verification. Its
> complexity will of course not work for larger values such as 16.
>
> Supports sorting networks currently up to length 6.
>
> More to come :)

This is great. A few notes:

* Spacing around operators is inconsistent, for Phobos please use the 
prevalent style.

* There's a bit too much foreplay, e.g. why introduce names for 
everything even when used once (e.g. "alias comp = binaryFun!less;").

* There should be a notion of at what point the networks become too 
bulky to be fast - 6-16 may be the limit.

* The arguments in conditionalSwap are a bit awkward, how about:

template conditionalSwap(indexes...)
{
   void conditionalSwap(less = "a < b", Range)(Range r) { ... }
}

That way the caller doesn't need to specify less and Range.

* There is a nice peephole optimization you could make. Consider:

r.conditionalSwap!("a < b", less, 0, 1, 1, 2)(r);

which needs to do

if (r[1] < r[0]) r.swapAt(0, 1);
if (r[2] < r[1]) r.swapAt(1, 2);

For types with no elaborate copy/assignment, it's more efficient to use 
a "hole"-based approach - assign the first element to a temporary and 
then consider it a hole that you fill, then leaving another hole:

if (r[1] < r[0])
   if (r[2] < r[0]) r.swapAt(0, 1, 2);
   else r.swapAt(0, 1);
else
   if (r[2] < r[1]) r.swapAt(1, 2);

with swapAt with three argument having this definition: auto t = r[a]; 
r[a] = r[b]; r[b] = r[c]; r[c] = t;

i.e. create a temporary (which creates a "hole" in the array) then fill 
it leaving another hole etc., until the last hole is filled with the 
temporary.

* I found no use for hybridSort, only for sortExactly. Then hybridSort 
is a two-liner the user may write.

> Could you please take a look at how to handle stability of "equal"
> elements?

I'm not sure. Does it suffice to always swap when the lhs index is less 
than the rhs index?


Andrei