Parallel Multitonic Sorting Networks.

This report is a study of the characteristics of multitonic sequences applied to parallel sorting networks. The main concern is the interconnections among the comparison levels of the sorting networks. A sorting network depends on various sorting algorithms and basic comparison element BCE implementation. A BCE is a device which can compare inputs and yields ordered outputs either in ascending order or in descending order. In order to facilitate analysis, the investigation is first confined to each BCE accepting two inputs only. With this restriction, sorting algorithms for parallel processing are described. Next, a new technique of graphic method is introduced, which helps the analysis of characteristics of multitonic sequences with respect to 2-sorters, and leads to the construction of perfect shuffle networks with 0 and 1 operations. Finally, the same technique of graphic method is also applied to construct perfect shuffle networks with BCEs that can accept three inputs.