Sorting nine inputs requires twenty-five comparisons

Michael Codish, Luis Cruz-Filipe, Michael Frank and Peter Schneider-Kamp   

Journal of Computer and System Sciences; 82 (3): 551-563, 2016

Abstract:

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. 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.

Available:    bibtex entry

Related sites:   e-print from arXiv.org   ACM Digital Library


Michael Codish
The Department of Computer Science
Ben-Gurion University of the Negev
PoB 653, Beer-Sheva, 84105, Israel
mcodish@cs.bgu.ac.il

© copyright notice