Title :
A modulo merge sorting network
Author :
Liszka, Kathy J. ; Batcher, Kenneth E.
Author_Institution :
Kent State Univ., OH, USA
Abstract :
The odd-even merge is a widely used and generally accepted merging network that uses O(N log2N) comparators with O(log2N) delay. A novel merging network is presented that generalizes the technique used in the odd-even merge. It is based on the division of the input keys by a specified modulus, not limited to 2. A special comparator is used in the final merge step that accepts m input lines and produces m sorted items, where m is the modulus selected for the merge. Alternatives are discussed that apply to the bitonic merging network
Keywords :
computer architecture; delays; merging; sorting; bitonic merging network; comparators; delay; merging network; modulo merge sorting network; odd-even merge; Computer architecture; Computer networks; Corporate acquisitions; Delay effects; Merging; Sorting;
Conference_Titel :
Frontiers of Massively Parallel Computation, 1992., Fourth Symposium on the
Conference_Location :
McLean, VA
Print_ISBN :
0-8186-2772-7
DOI :
10.1109/FMPC.1992.234892
