Finding Better Sorting Networks

Download or read book Finding Better Sorting Networks written by Sherenaz Waleed Al-Haj Baddar and published by . This book was released on 2009 with total page 75 pages. Available in PDF, EPUB and Kindle. Book excerpt: Sorting networks are cost-effective multistage interconnection networks with sorting capabilities. AKS Sorting networks sort N keys in C(logN) steps, but the constant C is so high as to render these networks impractical. The fastest Sorting networks designed so far use merge-sorting and sort N keys in O((logN)(logN)) steps. A network that sorts 16 keys in 9 steps was discovered by Van Voorhis. This network is faster than the 10-step merge-sorting network for 16 keys. This suggests that networks that are faster than merge-sorting networks can be designed. It is necessary to bridge the gap between the optimal impractical solutions and the practical solutions. This research aims at achieving this goal via finding a technique for designing faster Sorting networks, i.e. networks that require fewer steps than the corresponding merge-sorting networks. A zero/one case is a sequence of N binary keys. Using zero/one cases to help design Sorting networks, is advantageous since it simplifies the sorting task, and helps track the progress of sorting. To help synthesize and analyze Sorting networks, Batcher developed the software tool Sortnet, which utilizes zero/one cases. With the help of Sortnet, a three-phase technique for designing Sorting networks that are faster than the merge-sorting networks was developed. The technique can also be used to design faster sorting programs in parallel processors. This technique is illustrated with two network designs that are faster than the corresponding merge-sorting designs: an 18-key network using only 11 steps and a 22-key network using only 12 steps.