Title :
An Improved Lower Bound for Sorting Networks
Author :
Van Voorhis, David C.
Author_Institution :
Advanced Systems Development Division, IBM Corporation, Los Gatos, Calif. 95030.
fDate :
6/1/1972 12:00:00 AM
Abstract :
The minimum number of comparators S(N) required by an N-input sorting network is bounded below by S(N) ¿ N[log2 (N) - 1] + 0(1), as a consequence of the theorem S(N) ¿ S(N - 1) + [log2 (N)].
Keywords :
Circuit synthesis; Detectors; Electrons; Logic arrays; Network address translation; Operational amplifiers; Sorting; Switches; Switching circuits; Voltage; Bose-Nelson sorting problem; cellular logic; comparators; logic-in-memory arrays; sorting networks;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1972.5009021
