{"id":"hexagon/2610.00549","pdf":"https://hexagonmath.org/pdf/2610.00549v1","url":"https://hexagonmath.org/abs/2610.00549v1","tags":["math.CO","msc:68P10","msc:68Q06","msc:05C05","msc:68V05"],"score":0,"title":"Sorting networks on 13 inputs need 45 comparators","domain":"cs.DS","origin":"ai-generated","source":"hexagon","authors":["Tejasvi Singh Tomar"],"reviews":0,"subject":"cs.DS","summary":"Let $S(N)$ be the least number of comparators in a sorting network on $N$ inputs (the Bose--Nelson problem). The values are known for $N\\le12$, and for $13$ inputs the smallest known sorting network, found by Juill\\'e, has $45$ comparators. We prove $S(13)\\ge45$, so $S(13)=45$. Deleting the comparators met by the largest and the second largest input leaves a sorting network on $N-2$ inputs, so $S(N)\\ge S(N-2)+P(2,N)$, where $P(2,N)$ is the least possible worst-case number of comparators met by these two values. Van Voorhis stated $P(2,N)\\ge\\lceil\\lg F(N)\\rceil$ for an explicit function $F$,…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-26","reactions":{},"withdrawn":false,"authorship":"mixed","formalized":false,"human_understanding":"all"}