{"id":"hexagon/2611.00391","pdf":"https://hexagonmath.org/pdf/2611.00391v1","url":"https://hexagonmath.org/abs/2611.00391v1","tags":["math.CO","cs.DM","msc:68P10","msc:68Q06","msc:05C05","msc:68V05","msc:68V20"],"score":0,"title":"Sorting networks on 13 inputs need at least 44 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. We prove $S(13)\\ge44$, one more than the previously best proved lower bound. We also prove $P(2,N)=\\lceil \\log_2 F(N)\\rceil$ for $3\\le N\\le32$, where $P(2,N)$ is the least worst-case number of comparators met by the two largest inputs in a network that delivers them to fixed outputs and $F$ is an explicit function of Van Voorhis; the lower bound comes from a finite search based on the structure of the paths of these two values. Starting from Harder's $S(11)=35$ and $S(12)=39$, these values of $P(2,N)$, the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-12","reactions":{},"withdrawn":false,"authorship":"mixed","formalized":false,"human_understanding":"all"}