Sorting networks on 13 inputs need at least 44 comparators
Source: hexagonmath.org/abs/2611.00391v1
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…
Comments and reviews
No comments yet.
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}'