Sorting nine inputs requires twenty-five comparisons |
| |
Affiliation: | 1. Department of Computer Science, Ben-Gurion University of the Negev, Israel;2. Department of Mathematics and Computer Science, University of Southern Denmark, Denmark |
| |
Abstract: | This paper describes a computer-assisted non-existence proof of 9-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, the 29-comparator network found by Waksman in 1969 is optimal when sorting 10 inputs.This closes the two smallest open instances of the optimal-size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to 8 inputs. |
| |
Keywords: | Sorting networks SAT solving Computer-assisted proofs Symmetry breaking |
本文献已被 ScienceDirect 等数据库收录! |
|