Fixed Length Sorting via Sorting Networks.
Conditionally pairwise sort elements of Range r at indexes using comparison predicate less.
Hybrid sort r using networkSortUpTo if length of r is less-than-or-equal to networkSortMaxLength and std.algorithm.sorting.sort otherwise.
Sort range x of length n using a networking sort.
Sort static array x of length n using a networking sort.
Sort at most the first n elements of r using comparison less using a networking sort.
Largest length supported by network sort networkSortUpTo.
Static Iota. TODO Move to Phobos std.range.
TODO see some sizes are not supported, we should not have holes. Use http://www.angelfire.com/blog/ronz/Articles/999SortingNetworksReferen.html
TODO 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.
TODO Stability of equal elements: Need template parameter equalityStability? Scalar builtin values are always stable.
TODO There should be a notion of at what point the networks become too bulky to be fast - 6-16 may be the limit.
TODO 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 < r) r.swapAt(0, 1); if (r < r) 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 < r) if (r < r) r.swapAt(0, 1, 2); else r.swapAt(0, 1); else if (r < r) r.swapAt(1, 2);
with swapAt with three argument having this definition:
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.