Bounds to Complexities of Networks for Sorting and for Switching
David E. Muller, Franco P. Preparata · Journal of the ACM · 1975
A network which sorts n numbers, when used to sort numbers of only two sizes, 0 and 1, can be regarded as forming the n frontal (unite) symmetric Boolean functions of n arguments When sorting networks are constructed from comparator modules they have been widely conjectured to require (1) delay time or number of levels of order (log2n) 2, (2) size or number of elements of order n0og2n) ~, and (3) formula length or number of hterals of order n~°*2 ~ It IS proved constructively in the paper that, if one permits the use of negations in constructing the corresponding Boolean functions, these three measures of complexity can be reduced to the orders of log2n, n, and n ~, respectively The latter network, however, is Incapable of sorting numbers other than O's and rs and may be thought of as merely counting the number of Inputs which are 1 It is shown, however, that one may incorporate this network in a larger network which does sort and In time proportional to only logan This network is the first known example of a nonadaptive network capable of sorting in time less than (log2n) 2 CR CATEGORIES: 5 25, 5 31, 6 1 KEY WORDS AND PHRASES computational complexity, sorting, counting, symmetric Boolean functions, computation time, length of formula 1.Two basic operations often used in sorting networks are the formation of the maximum and the minimum of a pair of numbers.These operations are usually performed at the same time by a two-input, two-output device called a comparator module which may be regarded as being composed of two more basic elements.The first is a comparison element with binary output indicating which of the two inputs is larger, and the second is a crossover switch which is set by the output of the first element so as to place the larger number on one line and the smaller on the other.We may use the Boolean notation a V b and ab for the maximum and the minimum, respectively, of two numbers a and b.The convenience of this notation has been observed by several authors [1, 3], since Boolean expressions can be used in the analysis of sorting networks.The interpretation of these expressions, however, depends upon the domain of the variables.A network of comparator modules sorts n numbers if and only if, when interpreted as a network of AND and OR gates, it realizes the n frontal (unite) symmetric Boolean functions of n variables [3].This fact is easily seen, since a sorting network can also be used with numbers which are of just two sizes, 0 and 1.Conversely, if all input configurations of O's and l's are properly sorted, the output functions are uniquely defined as the frontal symmetric functions.These functions are also the ones which, when reinterpreted as ap-