The Design and Research of Lower-Cost Sorting Networks

[[abstract]]In this report, we prove that we can't construct a three-stage sorting network for sorting n data when the sizes of the largest sub-nets of the first stage and the third stage are less than or equal to n/3. This depicts that column sort algorithm can't be modified as a three-stage sorting network and preserve its parallelism. The result also shows that it's impossible to reduce the four-stage sorting steps to the three-stage sorting steps. Based on the attestation in this report, the researchers who investigate the sorting network algorithms and are interested in this domain will be benefited from this report. In 1994, Lee Tony T. proved that it's impossible to sort n data in a three-stage sorting network if the data are transposed from the first stage to the second stage and the numbers of sub-nets of the first and the second stages are larger than 2. In the report, we will remove all limitations in Lee's attestation, i.e. no matter how the data are transferred among the three stages, or the sizes of sub-nets in any specified stage are equal or not, we prove that we can't construct a three-stage sorting network when the sizes of the largest sub-nets of the first stage and the third stage are less than or equal to n/3. In addition, we propose an algorithm that is different from the current recursive-sorting networks which are based on the two-value or three-value sorting sub-nets. We call this algorithm as k-column sort algorithm. This algorithm can merge k equal-size sorted data based on the k-value sub-nets. We also derive the cost and delay of this algorithm. Currently the researches on sorting networks can be categorized into two classes: how to minimize the size of the sorting network to sort a fixed number of data and how to merge several sorted data into a sorted data. Based on this research, we can construct different networks to reduce the cost and delay. In the same time, we can have more alternatives to design the sorting networks.