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 (unate) symmetric boolean functions of n arguments. When sorting networks are constructed from comparator modules they appear to require: (1) delay time or number of levels of order (log of n to the base 2) squared, (2) size or number of elements of order (log of n to the base 2) squared, and (3) formula length or number of literals of order n (log of n to the base 2). 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 log of n to the base 2, n, and n to the 5th power respectively. The latter network however is incapable of sorting numbers and may be thought of as merely counting the number of inputs which are 1. One may incorporate this network, however, in a larger network which does sort and in time proportional to only log of n to the base 2. (Author)