The New Class of g-Chain Periodic Sorters |
| |
Authors: | Ronald I Becker David Nassimi Yehoshua Perl |
| |
Affiliation: | aDepartment of Mathematics, University of Cape Town, Rondebosch, 7700, South Africa;bDepartment of Computer and Information Science, New Jersey Institute of Technology, Newark, New Jersey, 07102 |
| |
Abstract: | Aperiodic sorteris a sorting network that is a cascade of a number of identicalblocks, where outputiof each block is inputiof the next block. Previously, Dowd, Perl, Rudolph, and Saks introduced thebalancedmerging network, withN=2kinputs/outputs and log Nstages of comparators. Using a very intricate proof, they showed that a cascade of log Nsuch blocks constitutes a sorting network. In this paper, we introduce a large class of merging networks with the same periodic property. This class contains 2N/2−1networks, whereN=2kis the number of inputs. The balanced merger is one network in this class. Other networks use fewer comparators. We provide a very simple and elegant correctness proof based on the recursive structure of the networks. |
| |
Keywords: | parallel sorting merging networks sorting networks periodic sorters |
本文献已被 ScienceDirect 等数据库收录! |
|