Accession Number : AD0721701

Title :   An Improved Lower Bound for the Bose-Nelson Sorting Problem.

Descriptive Note : Technical note,

Corporate Author : STANFORD UNIV CALIF STANFORD ELECTRONICS LABS

Personal Author(s) : Van Voorhis,David C.

Report Date : FEB 1971

Pagination or Media Count : 14

Abstract : The paper presents a constructive proof that the minimum number of comparators required for an N-input sorting network is at least the summation from K=1 to N (log of N to the base 2). This lower bound represents a linear improvement over the information-theoretic bound of (log of N factorial to the base 2). (Author)

Descriptors :   (*COMPUTER LOGIC, LOGIC CIRCUITS), COMPARATORS, DATA PROCESSING, INPUT OUTPUT DEVICES

Subject Categories : Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE