SORTING NETWORKS RE-VISITED
 
                           Kenneth E. Batcher
                Dept. of Mathematics and Computer Science
                         Kent State University
                             Kent OH 44244
 
 
ABSTRACT:  Networks that can sort in log-squared time were reported in 
1968: the networks perform merge-sorting with either odd-even merges or 
bitonic merges.  From the paper one might think there's something 
special about the number two:
 
(1) - each bitonic sequence is split into two bitonic sub-sequences;
 
(2) - odd-even merges are based on the indices of items modulo two;
 
(3) - each basic element compares keys of two items; and
 
(4) - each merge combines two sorted sequences into a sorted sequence.
 
We show that there's nothing really special about the number two: in 
each of the four instances one can substitute any larger integer for the 
number two.
 
We also compare bit-serial comparison elements with bit-parallel 
elements: besides using less hardware, a sorting network with bit-serial 
elements actually runs faster than a network with bit-parallel elements.
 
 
BIOGRAPHY:  Dr. Batcher received a B.S.E.E. degree from Iowa State 
University in 1957 and M.S. and Ph.D. degrees from the University of 
Illinois in 1962 and 1964, respectively.  He worked in the Computer 
Engineering Department of Goodyear Aerospace Corporation (now Lockheed-
Martin Tactical Defense Systems Division) for 28 years.  In 1989 he 
joined the faculty at Kent State University.  In 1990, he was awarded 
the Eckert-Mauchly Award from the ACM and the IEEE Computer Society "for 
the pioneering implementation of parallel computers and for 
contributions to interconnection network theory."  He is a Fellow in the 
ACM and a member of SIGARCH.