Finding Faster Sorting Networks

Sorting networks are cost-effective multistage interconnection networks with sorting capabilities. To help synthesize and analyze Sorting networks, the software tool Sortnet, which utilizes zero/one cases, was developed. 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. The technique is illustrated, in this book, 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.