Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Computer Sciences
Selection Networks, Nicholas Pippenger
Selection Networks, Nicholas Pippenger
All HMC Faculty Publications and Research
An upper bound asymptotic to $2n\log _e n$ is established for the number of comparators required in a network that classifies $n$ values into two classes, each containing $n / 2$ values, with each value in one class less than or equal to each value in the other. (The best lower bound known for this problem is asymptotic to $(n / 2)\log _2 n$.)