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

(32)

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

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)