New Bounds on Optimal Sorting Networks

DOI10.1007/978-3-319-20028-6_17MaRDI QIDQ3195693zbMATH OpenOpenAlexFDO

Authors Thorsten Ehlers, Mike Müller

Publication date 20 October 2015

Published in Evolving Computability (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Searching and sorting (68P10)

Abstract: We present new parallel sorting networks for $17$ to $20$ inputs. For $17,19,$ and $20$ inputs these new networks are faster (i.e., they require less computation steps) than the previously known best networks. Therefore, we improve upon the known upper bounds for minimal depth sorting networks on $17,19,$ and $20$ channels. Furthermore, we show that our sorting network for $17$ inputs is optimal in the sense that no sorting network using less layers exists. This solves the main open problem of [D. Bundala & J. Za'vodn'y. Optimal sorting networks, Proc. LATA 2014].

Recommendations

• Toward a lower bound for sorting networks
• scientific article; zbMATH DE number 1263220
• Optimal sorting networks
• Optimal-depth sorting networks
• On optimal parallelization of sorting networks
• scientific article; zbMATH DE number 4031004
• Bounds to Complexities of Networks for Sorting and for Switching
• Formally proving size optimality of sorting networks
• On the complexity of min-max sorting networks
• Improved sorting networks with O(log N) depth

Cites work

• A computer-assisted optimal depth lower bound for nine-input sorting networks
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Optimal sorting networks
• Sorting networks: the end game
• Using symmetry and evolutionary search to minimize sorting networks

Cited in

(27)

• A generalization of the 0-1 principle for sorting
• Formally proving size optimality of sorting networks
• New results in minimum-comparison sorting
• Sorting-based selection algorithms for hypercubic networks
• An improved subsumption testing algorithm for the optimal-size sorting network problem
• Sorting networks: to the end and back again
• Optimizing sorting algorithms by using sorting networks
• A theoretical look at \textsc{Electre Tri}-nB and related sorting models
• Sorting networks: the end game
• A computer-assisted optimal depth lower bound for nine-input sorting networks
• 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
• The Complexity of Sorting with Networks of Stacks and Queues
• scientific article; zbMATH DE number 4031004 (Why is no real title available?)
• scientific article; zbMATH DE number 1263220 (Why is no real title available?)
• On the complexity of min-max sorting networks
• A super-logarithmic lower bound for hypercubic sorting networks
• The half cleaner lemma: constructing efficient interconnection networks from sorting networks
• A sorting network on trees
• Optimal sorting networks
• Applying sorting networks to synthesize optimized sorting libraries
• Improved sorting networks with O(log N) depth
• An 11-step sorting network for 18 elements
• Improved layout of the odd-even sorting network
• Sorting nine inputs requires twenty-five comparisons
• Bounds on the size of test sets for sorting and related networks

This page was built for publication: New Bounds on Optimal Sorting Networks

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