• DocumentCode
    959279
  • 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.
  • Issue
    6
  • fYear
    1972
  • fDate
    6/1/1972 12:00:00 AM
  • Firstpage
    612
  • Lastpage
    613
  • 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;
  • fLanguage
    English
  • Journal_Title
    Computers, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0018-9340
  • Type

    jour

  • DOI
    10.1109/TC.1972.5009021
  • Filename
    5009021
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=959279