October 2026 · Preprint

Sorting networks on 14 inputs need 50 comparators

Abstract

Let S(N) be the least number of comparators in a sorting network on N inputs. Its value is known for N ≤ 13, and for 14 inputs it was known that 49 ≤ S(14) ≤ 51. We prove S(14) ≥ 50, so S(14) is 50 or 51; as a consequence, S(16) ≥ 59. The proof uses S(13) = 45 to restrict the paths of the largest and the smallest value in a sorting network on 14 inputs with 49 comparators. After a computation, these restrictions leave a few thousand possible prefixes of such a network, up to symmetry. A computer search shows that none of them can be completed to such a network. The search uses Harder's Huffman bound (arXiv:2012.04400) and the weighted two-value bound from our proof of S(13) = 45; several of our programs are modifications of Harder's code. A separately written program checks the certificates, and S(14) ≥ 50 is also derived in Lean 4 from bounds certified outside Lean; part of the derivation runs as compiled code.

In plain words

Some sorting methods compare pairs of numbers on a schedule fixed in advance, swapping each pair that is out of order. Each compare-and-swap is a comparator, and such methods are called sorting networks. Because the schedule never depends on the numbers, they suit parallel sorting. In 1962 Bose and Nelson asked how few comparators such a network needs. For 14 numbers the smallest network known has 51 comparators, and this paper proves with computer searches that at least 50 are needed, so the minimum is 50 or 51.

Fourteen horizontal wires crossed by 51 vertical comparator bars in ten layers. Thick magenta lines run from the left end of every wire through black comparators in the first four layers to the bottom wire, labelled "largest"; thick blue lines run in the same way to the top wire, labelled "smallest". The other comparators, including all those in the last six layers, are grey.
Illustration of a sorting network on 14 inputs with 51 comparators in ten layers, from Bert Dobbelaere’s list of the smallest known networks. A vertical bar is a comparator: it takes the values on the two wires it joins and sends the larger value to the lower wire. Magenta lines show the path the largest value would take from each of the 14 inputs to the bottom wire; blue lines show the same for the smallest value, which ends on the top wire. The comparators on these paths are black. The proof that every sorting network on 14 inputs has at least 50 comparators starts from the same kind of paths: if one had 49, every path of the largest value, and every path of the smallest, would meet at most four comparators.

Formal statement and axioms

Each main result as stated in Lean, copied verbatim from the published package, with the axioms that the proof rests on. Lean v4.35.0-rc3, Mathlib c55e6e786f49. The package.

Sortnet.S14.S14_ge_50_N

S(14) ≥ 50: with compiled code

theorem Sortnet.S14.S14_ge_50_N :
    Sortnet.S14.coreTableC.Valid →
    (∀ i ∈ Sortnet.S14.Wed.done, (Sortnet.S14.Wed.TLf i).Valid) →
    Sortnet.S14.S14Statement
Definitions used in the statement
def S14Statement : Prop := ∀ net : Network 14, net.Sorts → 50 ≤ net.length
structure Comparator (n : Nat) where
  i : Fin n
  j : Fin n
  lt : i < j
  deriving DecidableEq
def Comparator.apply {n : Nat} (c : Comparator n) (v : Fin n → Nat) : Fin n → Nat :=
  fun k => if k = c.i then min (v c.i) (v c.j) else if k = c.j then max (v c.i) (v c.j) else v k
abbrev Network (n : Nat) := List (Comparator n)
def Network.eval {n : Nat} (net : Network n) (v : Fin n → Nat) : Fin n → Nat :=
  net.foldl (fun w c => c.apply w) v
def Network.Sorts {n : Nat} (net : Network n) : Prop :=
  ∀ v : Fin n → Nat, ∀ a b : Fin n, a ≤ b → net.eval v a ≤ net.eval v b
def bitSet (n K : ℕ) : Set (Vec n) := {v | Nat.testBit K (code v) = true}
structure Table where
  cnt : ℕ
  ent : ℕ → ℕ × ℕ × ℕ
def Table.Valid (T : Table) : Prop :=
  ∀ i < T.cnt, ((T.ent i).1 = 10 ∨ (T.ent i).1 = 11) → LB (bitSet (T.ent i).1 (T.ent i).2.1) (T.ent i).2.2

Source: Zenodo record 23632985, lean_s14_tools.tar.gz/lean_s14/assembly_n/S14AssemblyN.lean:37-40.

Axioms, as Lean reports them: propext, Classical.choice, Quot.sound and 43,100 more, for example Sortnet.certOK_harder11._native.native_decide.ax_1_1, Sortnet.S14.CSD.n_V2164_10._native.native_decide.ax_1_1 and Sortnet.S14.CSD.n_V2202_12._native.native_decide.ax_1_1. Each of these 43,100 axioms comes from a check that runs as compiled code (native_decide). The full report is recorded in zenodo:23632985/lean_s14_tools.tar.gz/lean_s14/assembly_n/assembly_out.txt:6-43108.