Generalized Recursive Sorting Networks
T.T. Lee · Journal of Parallel and Distributed Computing · 1994
A class of recursive sorting networks based on mod(s) m-merging, a generalization of Batcher′s odd-even merging, is studied in this paper. Iterative decomposition of a sorter into smaller comparator modules, an equivalent problem but in a different setting, is also resolved based on the scheme proposed here. We first show that it is impossible to generalize the principle of odd-even merging in a three-stage network. Then the condition on generalized mod(s) m-merging with four stages is proven. This scheme degenerates to the three-stage odd-even merging network when m = 2 and s = 2. An algorithm for computing the optimal configuration is also given. Applications of this sorting network include parallel relational database computers and modular construction of sorting networks for large packet switches.