AN 11-STEP SORTING NETWORK FOR 18 ELEMENTS
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 Θ(Nlog2N) 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.
References
- D. C. Van Voorhis, Efficient sorting networks, Ph. D. Thesis, Stanford University, 1972 . Google Scholar
K. E. Batcher , Sorting networks and their applications, Spring Joint Computer Conference, AFIPS Proc. (1968) pp. 307–314. Google Scholar- Combinatorica 3, 1 (1983). Crossref, ISI, Google Scholar
- K. E. Batcher and S. W. Al-Haj Baddar, Sortnet: a program for building sorting networks, Technical Report No. TR-KSU-CS-2008-01, Department of Computer Science, Kent State University, February 2008 . Google Scholar
D. E. Knuth , The Art of Computer Programming: Volume 3: Sorting and Searching, 2nd edn. (Addison-Wesley Longman, USA, 1998) pp. 225–228. Google ScholarK. H. Rosen , Discrete Mathematics and its Applications, 5th edn. (McGraw-Hill Companies, USA, 2003) pp. 520–525. Google Scholar


