Ads by Google

Christian Borgelt's Web Pages

sortnet.ipynb | (14 kb) | Python / Jupyter Notebook |

Sorting networks are special comparator networks.
A comparator network consists of *wires* or *lanes*
carrying values and *comparators* or *conditional swap devices*
connecting pairs of wires. A comparator swaps values between wires
if they are not in a desired order. Comparators connecting disjoint
pairs of wires may be executed in parallel, due to which they can
be arranged in *layers* (of comparators executable in parallel).
The *size* of a sorting network is its number of comparators,
and its *depth* is its number of layers.

Sorting networks are sorting algorithms with a fixed execution structure, that is, their execution structure is independent of the data to be sorted. This property makes them suitable for hardware implementations.

The Python code provided here as a Jupyter Notebook covers odd-even merge, pairwise and bitonic sorting networks. A sorting network is represented as list of layers, each of which is a list of pairs of integers, which indicate the wires that are connected by a comparator. In addition to creation functions, a function is provided with which a sorting network can be applied to an input list of comparable objects, to sort the list into either increasing or decreasing order.

The original papers introducing the covered sorting networks are:

**Sorting Networks and Their Application**

Ken E. Batcher

*Proc. AFIPS Spring Joint Computer Conference (Atlantic City, NJ)*, 307-314

doi:10.1145/1468075.1468121**The Pairwise Sorting Network**

Ian Parberry

*Parallel Processing Letters*2(2,3):205-211

doi:10.1142/S0129626492000337