Sorting networks on 13 inputs need at least 44 comparators

Abstract

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 ≤ 12, and the best proved bounds for 13 inputs have been 43 ≤ S(13) ≤ 45. We prove S(13) ≥ 44. Deleting the comparators met by the largest and the second largest input leaves a sorting network on N − 2 inputs, so S(N) ≥ S(N − 2) + P(2, N), where P(2, N) is the least possible worst-case number of comparators met by these two values. In 1972 Van Voorhis stated P(2, N) ≥ ⌈log₂ F(N)⌉ for an explicit function F, but a 2026 audit showed that his proof is invalid. We determine P(2, N) by computer instead. We show that the number of comparators met by the two values in each run is determined by the binary tree formed by the paths of the maximum, the comparators that these paths pass, and the depths at which the second maximum enters a forest of further comparators. This reduces the inequality P(2, N) ≤ L to a finite search. For N = 13 and L = 8 only 25 cases remain, and none of them can be completed, so P(2, 13) = 9, and Harder's S(11) = 35 gives S(13) ≥ 44. Independent checks confirm P(2, 13) = 9: a second implementation with its own lemmas, an exhaustive search over networks that does not use our structural reduction, and an integer program for each case. The same searches give P(2, N) = ⌈log₂ F(N)⌉ for 3 ≤ N ≤ 27, which proves the lower bounds on S(N) for 13 ≤ N ≤ 27 listed in Dobbelaere's public table.