An Improved Lower Bound for the Bose-Nelson Sorting Problem

摘要

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)