THE NEW CLASS OF G-CHAIN PERIODIC SORTERS

A periodic sorter is a sorting network that is a cascade of a number o r identical blocks, where output i of each block is input i of the nex t block. Previously, Dowd, Perl, Rudolph, and Saks introduced the bala nced merging network, with N = 2(k) inputs/outputs and log N stages of comparators. Using a very intricate proof, they showed that a cascade of log N such blocks constitutes a sorting network. In this pager, we introduce a large class of merging networks with the same periodic pr operty. This class contains 2(N/2-1) networks, where N = 2(k) is the n umber of inputs. The balanced merger is one network in this class. Oth er networks use fewer comparators. We provide a very simple and elegan t correctness proof based on the recursive structure of the networks, (C) 1998 Academic Press.