Abstract
A sorting network for N items, or an N-sorter, is a circuit with inputs I = {i1, i2, ..., iN} and outputs Ø = {o1, o2, ..., oN}, such that Ø is a monotonically increasing permutation of I. Sorting networks can be constructed using ranks of a basic cell called a comparator, which is essentially a 2-sorter. For example, the 4-sorter depicted in Fig. 1 employs five comparators, which all emit their larger input on their higher output lead.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1972 Plenum Press, New York
About this chapter
Cite this chapter
Van Voorhis, D.C. (1972). Toward a Lower Bound for Sorting Networks. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds) Complexity of Computer Computations. The IBM Research Symposia Series. Springer, Boston, MA. https://doi.org/10.1007/978-1-4684-2001-2_12
Download citation
DOI: https://doi.org/10.1007/978-1-4684-2001-2_12
Publisher Name: Springer, Boston, MA
Print ISBN: 978-1-4684-2003-6
Online ISBN: 978-1-4684-2001-2
eBook Packages: Springer Book Archive