| 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: