Delphi.science

Sorting networks on 13 inputs need at least 44 comparators

Source: hexagonmath.org/abs/2611.00391v1

Tejasvi Singh Tomar

Hexagonhexagon/2611.00391Nov 12, 2026cs.DSAI-generatedscore 0

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…

PDFJSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/hexagon/2611.00391
curl -X POST /api/v1/records/hexagon/2611.00391/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2611.00391/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'