Optimal sorting networks

DOI10.1007/978-3-319-04921-2_19MaRDI QIDQ5404915zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Daniel Bundala, Jakub Závodný

Publication date 31 March 2014

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.6271

Mathematics Subject Classification ID

Searching and sorting (68P10)

Abstract: This paper settles the optimality of sorting networks given in The Art of Computer Programming vol. 3 more than 40 years ago. The book lists efficient sorting networks with n <= 16 inputs. In this paper we give general combinatorial arguments showing that if a sorting network with a given depth exists then there exists one with a special form. We then construct propositional formulas whose satisfiability is necessary for the existence of such a network. Using a SAT solver we conclude that the listed networks have optimal depth. For n <= 10 inputs where optimality was known previously, our algorithm is four orders of magnitude faster than those in prior work.

Recommendations

• Optimal-depth sorting networks
• New Bounds on Optimal Sorting Networks
• Sorting networks: to the end and back again
• A computer-assisted optimal depth lower bound for nine-input sorting networks
• Sorting nine inputs requires twenty-five comparisons

Cited in

(29)

• Using symmetry and evolutionary search to minimize sorting networks
• Sorting with Complete Networks of Stacks
• Improved layout of the odd-even sorting network
• Sorting networks: to the end and back again
• Sorting out single-crossing preferences on networks
• Sorting-based selection algorithms for hypercubic networks
• scientific article; zbMATH DE number 4031004 (Why is no real title available?)
• Sorting and counting networks of arbitrary width and small depth
• New Bounds on Optimal Sorting Networks
• A computer-assisted optimal depth lower bound for nine-input sorting networks
• Constructing sorting networks from k-sorters
• Sorting on PRAMs with reconfigurable buses
• scientific article; zbMATH DE number 808799 (Why is no real title available?)
• On the complexity of min-max sorting networks
• The half cleaner lemma: constructing efficient interconnection networks from sorting networks
• Improved sorting networks with O(log N) depth
• Optimal conclusive sets for comparator networks
• Synchronous counting and computational algorithm design
• Optimal-depth sorting networks
• Merging almost sorted sequences yields a 24-sorter
• A Robust Sorting Network
• Sorting nine inputs requires twenty-five comparisons
• Formalizing size-optimal sorting networks: extracting a certified proof checker
• Pairwise cardinality networks
• Optimizing sorting algorithms by using sorting networks
• Formally proving size optimality of sorting networks
• Combinatorial search in two and more rounds
• Sorting networks: the end game
• Applying sorting networks to synthesize optimized sorting libraries

This page was built for publication: Optimal sorting networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5404915)