98 citations · 385 across the 33 of their papers we have counts for
4 papers · 1 filter
Optimal-Depth Sorting Networks
Daniel Bundala, Michael Codish, Luís Cruz-Filipe +2
We solve a 40-year-old open problem on the depth optimality of sorting networks. In 1973, Donald E. Knuth detailed, in Volume 3 of "The Art of Computer Programming", sorting networ…
Sorting Networks: the End Game
Michael Codish, Luís Cruz-Filipe, Peter Schneider-Kamp
This paper studies properties of the back end of a sorting network and illustrates the utility of these in the search for networks of optimal size or depth. All previous works focu…
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…
The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes
Michael Codish, Luis Cruz-Filipe, Peter Schneider-Kamp
Previous work identifying depth-optimal -channel sorting networks for is based on exploiting symmetries of the first two layers. However, the naive generate-an…