Sorting Network Generator
A sorting network is a fixed sequence of compare-and-swap operations that sorts any input without ever looking at the values — which is what makes it implementable in hardware, or in code with no branches at all. Proving one correct sounds like an infinite job, until the zero-one principle turns it into a finite one: a network that sorts every sequence of zeroes and ones sorts everything. This builds a network and runs all of those cases.
What this generator does
Constructs the comparator sequence for the chosen network, groups it into layers of comparators that share no wire, and then runs every possible binary input through it to confirm the output is always sorted.
How to use this tool
- Choose how many values the network should sort.
- Pick a construction: Batcher's is shallow, insertion is simple.
- Read the layers — everything in one layer runs at the same time.
- Compare the depth of the two constructions on the same width.
Understanding the controls
- How many wires
- Between 2 and 8 values. The exhaustive check runs two to the power of this, so eight wires means 256 test inputs — all of them run.
- Construction
- Batcher's odd-even mergesort is shallow and is what hardware would use. The insertion network is easy to follow and deliberately not efficient, which makes the comparison worth making.
Common use cases
- Producing a comparator sequence for a branch-free sort
- Teaching the zero-one principle with an exhaustive check
- Comparing network constructions by size and depth
- Generating sorting networks for hardware or shader code
- Showing why fixed comparison sequences can sort at all
How this generator works
The comparators are generated by the chosen construction and then grouped greedily into layers, where every comparator in one layer touches wires no other comparator in that layer touches — so a layer runs in one parallel step, and the number of layers is the network's depth. Correctness rests on the zero-one principle: because a comparator network is oblivious, sorting every sequence of zeroes and ones implies sorting every sequence at all. That turns an infinite claim into a finite one, and every case is run before display.
Randomness and fairness
Nothing here is random. A width and a construction give exactly one network.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- The width is capped at eight because the exhaustive check doubles with each extra wire.
- Batcher's construction is shallow but not optimal: for small widths, hand-found networks use fewer comparators.
- The layering is greedy, so it gives a valid parallel schedule rather than provably the shallowest one.
- Sorting networks are fixed-size: a network for eight values cannot sort seven or nine.
Privacy and your data
The network is built in your browser and nothing you choose is transmitted, stored or included in analytics.
Related generators
- Sorting Algorithm Trace GeneratorAn array, an algorithm, and the state after every pass, with the comparison and move counts that distinguish the three.
- Complexity Comparison GeneratorTwo algorithms compared at every input size, with the crossover where better growth finally beats a large constant.
- Binary Search Scenario GeneratorSorted lists with the full binary search trace, every step's range shown, and the logarithmic bound as the check.
- Test Matrix GeneratorTurn parameters and their values into a test matrix — full factorial, a random sample, or all-pairs coverage in a fraction of the cases.