preprint · arXiv (Cornell University) · 2014

Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten)

Michael Codish, Luı́s Cruz-Filipe, Michael Frank, Peter Schneider–Kamp

Cited by 37Open access

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, we obtain that 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. The proof involves a combination of two methodologies: one based on exploiting the abundance of symmetries in sorting networks, and the other based on an encoding of the problem to that of satisfiability of propositional logic. We illustrate that, while each of these can single-handedly solve smaller instances of the problem, it is their combination that leads to the more efficient solution that scales to handle 9 inputs.

Cite this paper

APA 7

Codish, M., Cruz-Filipe, L., Frank, M., & Schneider–Kamp, P. (2014). Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten). arXiv (Cornell University), 186–193. https://doi.org/10.1109/ictai.2014.36

MLA 9

Codish, Michael, et al. “Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten).” arXiv (Cornell University), 2014, pp. 186–93, https://doi.org/10.1109/ictai.2014.36.

Chicago

Codish, Michael, Luı́s Cruz-Filipe, Michael Frank, and Peter Schneider–Kamp. 2014. “Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten).” arXiv (Cornell University): 186–93. https://doi.org/10.1109/ictai.2014.36.

Harvard

Codish, M. et al. (2014) ‘Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten)’, arXiv (Cornell University), pp. 186–193. Available at: https://doi.org/10.1109/ictai.2014.36.

BibTeX

@misc{codish2014twenty,
  title = {{Twenty-Five Comparators Is Optimal When Sorting Nine Inputs (and Twenty-Nine for Ten)}},
  author = {Codish, Michael and Cruz-Filipe, Luı́s and Frank, Michael and Schneider–Kamp, Peter},
  journal = {arXiv (Cornell University)},
  pages = {186--193},
  year = {2014},
  doi = {10.1109/ictai.2014.36}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.