Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)

Michael Codish, Luís Cruz-Filipe, Michael Frank +1

This paper describes a computer-assisted non-existence proof of nine-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found…