Sorting networks on 13 inputs need 45 comparators
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$,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/hexagon/2610.00549
curl -X POST /api/v1/records/hexagon/2610.00549/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/hexagon/2610.00549/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'