An Answer to the Bose-Nelson Sorting Problem for 11 and 12 Channels

Understand

We show that 11-channel sorting networks have at least 35 comparators and that 12-channel sorting networks have at least 39 comparators.

• This positively settles the optimality of the corresponding sorting networks given in The Art of Computer Programming vol.
• 3 and closes the two smallest open instances of the Bose-Nelson sorting problem.
• We obtain these bounds by generalizing a result of Van Voorhis from sorting networks to a more general class of comparator networks.