Bounds to Complexities of Networks for Sorting and for Switching

Publisher Website
Google Scholar
Abstract
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 func- tions, these three measures of complexity can be reduced to the orders of log2n, n, and n ~, respec- tively 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

This publication has 1 reference indexed in Scilit: