Copyright © 2025 by David K. Zhang. Released under the MIT License.
Comparator networks, also known as sorting networks, are fast algorithms for sorting or accumulating a fixed number of inputs. ComparatorNetworks.jl is a Julia package for discovering, analyzing, testing, and optimizing comparator networks.
A comparator network consists of horizontal wires and an ordered sequence of vertical comparators. Each comparator connects two wires and represents an operation, such as minmax or TwoSum, that takes and returns two values. Comparator networks are called sorting networks when used to sort their input data, but they can also be applied to other tasks, such as partial sorting, median selection, and high-precision arithmetic.
Finding optimal sorting networks is a notoriously hard combinatorial optimization problem. The optimal number of comparators in a sorting network remains unknown as of 2025, even for as few as 13 inputs. ComparatorNetworks.jl implements heuristic optimization algorithms based on simulated annealing to find comparator networks of minimal length (number of comparators) and depth (number of sequential dependencies) for a variety of tasks.
Note: ComparatorNetworks.jl is currently under active development. The function names and interfaces shown below may change in future releases.
Suppose we want to find a comparator network that sorts every possible permutation of 3 inputs. We first set up a condition object to represent the desired condition. Then, we call generate_comparator_network(condition) to find a random comparator network that satisfies the condition.
using ComparatorNetworks
condition = PassesAllTests(
[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)],
minmax, issorted)
network = generate_comparator_network(condition)
display(network)
This will return one of several possible outputs:
or
or
or
In the Julia REPL, this will display in textual form, e.g., ComparatorNetwork{3}(Tuple{UInt8, UInt8}[(0x02, 0x03), (0x01, 0x03), (0x01, 0x02)]). In Jupyter, this will display as a graphical SVG file, as shown above.