New Bounds on Optimal Sorting Networks
Authors:
Preprint
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].
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- Sorting Networks: The End Game2015
- The Quest for Optimal Sorting Networks: Efficient Generation of Two-Layer Prefixes2014
- AN 11-STEP SORTING NETWORK FOR 18 ELEMENTSParallel Processing Letters, 2009
- A computer-assisted optimal depth lower bound for nine-input sorting networksTheory of Computing Systems, 1991