Optimal Sorting Networks

Most sorting you have seen looks at the data: it compares two numbers, sees which is bigger, and decides what to do next. A sorting network is stranger. It is a fixed wiring diagram of compare-and-swap operations, decided in advance, that never branches on the values it sees.

Picture a few horizontal wires, one per number. Across them sit comparators: each connects two wires and, when a value flows through, it puts the smaller one on the upper wire and the larger on the lower one. Run any input through the same frozen sequence of comparators and it comes out sorted — always, no exceptions, no decisions made along the way.

The remarkable question is not whether such a circuit exists, but how small it can be. What is the fewest comparators that still sorts every input? For most sizes, the honest answer is: nobody knows for sure — the best networks we have were found by enormous computer searches, and proving they are optimal is still open.

Below is the optimal sorting network for 4 wires: exactly 5 comparators, arranged in 3 depth-layers. Press Step to fire one comparator at a time — it lights up the two wires it touches and turns red when it actually swaps. Press New input to scramble the values and watch the same fixed sequence sort them again.

<p class="hint">{{hint}}</p>
<div class="wires" id="wires"></div>
<div class="status" id="status">{{press_step}}</div>
<div class="btns">
  <button id="step" type="button">{{btn_step}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="shuffle" type="button" class="ghost">{{btn_new_input}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.wires { display: flex; flex-direction: column; gap: 10px; margin: .6rem 0; }
.wire { display: flex; align-items: center; gap: 8px; }
.wlabel { width: 22px; font: 600 13px ui-monospace, monospace; color: #888; }
.cell { width: 44px; height: 44px; display: flex; align-items: center; justify-content: center;
        font: 700 18px ui-monospace, monospace; border-radius: 8px; background: #e8eef3;
        color: #1d3557; border: 1px solid #cdd9e3; transition: all .18s; }
.cell.active { background: #1d3557; color: #fff; border-color: #1d3557; transform: scale(1.08); }
.cell.swapped { background: #e63946; color: #fff; border-color: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Here is the punchline you can feel by clicking: the steps never change. The network does not look at your numbers to decide what to do — it runs the identical 5 comparators no matter what, and the output is always sorted. That is why these circuits are called oblivious, and it is exactly what makes them easy to bake into hardware and parallel machines. Sorting 4 items optimally takes 5 comparators; for larger sizes, the optimal count is the hard part.

The deep fact that makes everything checkable is the zero-one principle: a network sorts all inputs if and only if it sorts every input made only of 0s and 1s. So to test a candidate network on n wires, you do not try every ordering — you try the $2^{n}$ binary inputs. Checking a given network is therefore easy. Finding the smallest one is the monster.

• Two things we want to minimize. The size is the total number of comparators; the depth is the number of parallel layers (how fast it runs on hardware). A network can be small but deep, or shallow but wasteful.
• Known only for small n. The optimal size is settled for n up to 12; values like S(9) = 25 and S(10) = 29 were only nailed down in 2014. The optimal depth is known a little further. Beyond that, we have best-known networks but no proof they are optimal — it is an open problem.
• Found by machine. The record networks come from gigantic computer searches — exhaustive enumeration pruned by symmetry, and modern SAT solvers that encode "is there a sorting network of size k?" as a logic formula. The search space explodes, which is why progress is measured one value of n at a time.
• The combinatorial wall. The number of candidate networks grows astronomically with n, and verifying optimality means ruling out every smaller network — a search that is exactly the kind of exhaustive hunt at the heart of P vs NP.

So the status is split: easy to verify, brutally hard to optimize. For four wires the answer is a clean 5; push to a few dozen wires and the true minimum slips beyond what anyone has been able to prove.

A sorting network's superpower is that it has no branches: the same operations run every time, in a predictable order. That is precisely what fast and secret hardware wants.

• GPUs and parallel hardware: thousands of cores hate unpredictable branches. Networks like the bitonic sorter run a fixed schedule of compare-and-swaps, making them a staple of GPU sorting.
• Circuits and FPGAs: a sorting network is a circuit. Its comparators map directly onto gates, giving sorters that run at line speed inside chips.
• Secure and private computation: when data is encrypted, you must not branch on it. Oblivious networks sort without ever revealing which value was bigger — essential for cryptography and secure multiparty protocols.
• Signal processing: small fixed networks compute medians and rank filters for image and audio pipelines, where a tiny optimal network saves real silicon.

And the search for optimal networks is itself a showcase for how far brute force and SAT solving can push a hard combinatorial question — a living example of computing chipping away at a problem one size at a time.

A sorting network is a small miracle: one frozen list of swaps that sorts everything, deciding nothing along the way. Thanks to the zero-one principle, checking that a network sorts is easy. Yet finding the smallest one is so hard that the optimal size is pinned down only for a handful of small sizes — and for the rest, our best networks are records found by machine, not theorems.

That gap is the whole story of this site in miniature: a problem where confirming an answer is trivial but discovering the best answer demands a search that quickly outruns us. The next time you sort a list, remember there is a tiny perfect circuit that could do it too — and that for all but the smallest cases, nobody can yet prove how small "perfect" really is. It is P vs NP wearing a wiring diagram.