nxt.algorithm.sortn

Fixed Length Sorting via Sorting Networks.

Members

Functions

hybridSort
auto hybridSort(Range r)

Hybrid sort r using networkSortUpTo if length of r is less-than-or-equal to networkSortMaxLength and std.algorithm.sorting.sort otherwise.

networkSortExactly
auto networkSortExactly(T[n] x)

Sort static array x of length n using a networking sort.

networkSortExactly
auto networkSortExactly(Range r)

Sort range x of length n using a networking sort.

networkSortUpTo
auto networkSortUpTo(Range r)

Sort at most the first n elements of r using comparison less using a networking sort.

See Also

Meta

License

Boost License 1.0.

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[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 = ra; ra = rb; rb = rc; rc = 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.