An Improved Lower Bound for the Bose-Nelson Sorting Problem.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1971
- Accession Number
- AD0721701
Entities
People
- David C. Van Voorhis
Organizations
- Stanford University