Sorting nine inputs requires twenty-five comparisons

作者：

Highlights：

• Twenty-five comparators are minimal to sort nine inputs.

• Twenty-nine comparators are minimal to sort ten inputs.

• New symmetry-breaking results control the growth of the search space.

• Optimized and parallelized algorithms for generating size-optimal sorting networks.

• Use of SAT-solving to speed up the last part of the computation.

摘要

•Twenty-five comparators are minimal to sort nine inputs.•Twenty-nine comparators are minimal to sort ten inputs.•New symmetry-breaking results control the growth of the search space.•Optimized and parallelized algorithms for generating size-optimal sorting networks.•Use of SAT-solving to speed up the last part of the computation.

论文关键词：Sorting networks,SAT solving,Computer-assisted proofs,Symmetry breaking

论文评审过程：Received 27 October 2014, Revised 10 November 2015, Accepted 30 November 2015, Available online 11 December 2015, Version of Record 29 December 2015.

论文官网地址：https://doi.org/10.1016/j.jcss.2015.11.014