AN 11-STEP SORTING NETWORK FOR 18 ELEMENTS
- 1 March 2009
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in Parallel Processing Letters
- Vol. 19 (01) , 97-103
Abstract
Sorting networks are cost-effective multistage interconnection networks with sorting capabilities. These networks theoretically consume Θ( NlogN ) comparisons. However, the fastest implementable sorting networks built so far consume Θ( Nlog 2 N ) comparisons, and generally, use the Merge-sorting strategy to sort the input. An 18-element network using the Merge-sorting strategy needs at least 12 steps — here we show a network that sorts 18 elements in only 11 steps.Keywords
This publication has 1 reference indexed in Scilit:
- Sorting inc logn parallel stepsCombinatorica, 1983