ANN: SortingNetworks package

package
announcement

#1

This package exports swapsort, a function which uses conditional swaps to sort the input. There are realizations for 2…25 arguments. These functions return a tuple with the values in ascending order. There are versions that accept a flat tuple as well as direct arguments; the forms taking multiple arguments are faster than the forms that expect a tuple.

Pkg.update()
Pkg.add("SortingNetworks")
using SortingNetworks

sorted = swapsort(a, b, c, d, e)
sorted = swapsort( (a, b, c, d, e) )

SortingNetworks.jl


#2

Can you give a brief description of the kinds of problems where this approach is useful? Just curious.


#3

Apply wherever the same small number of variable-valued items are being sorted.

Julia provides minmax(a,b) == (min(a,b), max(a,b)). I find that I use minmidmax(a,b,c) frequently, and it is much, much faster this way. Some quick statistical estimates use both the values as observed and then sorted.

Many sorts of algorithms rely on subdivision, and some of those need to sort a number of items related to the items handled in [one of] the smallest subdivision[s]. When the inside part is designed to handle 2…16 items, these sorting functions are a big win. One natural example is sorting itself; some sorting algorithms subdivide so most of the work is with a small number of items. That behavior is also evident in some selection algorithms: select the k largest or [probably] select the k largest of n.

The functions I gave are organized in blocks. There are between-block dependencies, so the blocks are performed sequentially. Within each block, each statement (line) is independent of the others. On system architectures that will process the internals of block in parallel, there is additional throughput gained. Even on less flexible systems, where this is useable and the code is often visited, it brings noticeable advantage.