Bounds to Complexities of Networks for Sorting and for Switching

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.