An upper bound asymptotic to $2n_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)_2 n$.)
%0 Journal Article
%1 pippenger91
%A Pippenger, Nicholas
%D 1991
%I SIAM
%J SIAM Journal on Computing
%K algorithm sorting sorting.network
%N 5
%P 878--887
%R 10.1137/0220054
%T Selection Networks
%V 20
%X An upper bound asymptotic to $2n_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)_2 n$.)
@article{pippenger91,
abstract = {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$.)},
added-at = {2016-11-06T12:46:10.000+0100},
author = {Pippenger, Nicholas},
biburl = {https://www.bibsonomy.org/bibtex/234bc8db091cc1305fe2e52692df97481/ytyoun},
doi = {10.1137/0220054},
interhash = {ae08ec7a844f07d2ca1280edee5eb665},
intrahash = {34bc8db091cc1305fe2e52692df97481},
journal = {{SIAM} Journal on Computing},
keywords = {algorithm sorting sorting.network},
month = oct,
number = 5,
pages = {878--887},
publisher = {SIAM},
timestamp = {2016-11-08T08:59:35.000+0100},
title = {Selection Networks},
volume = 20,
year = 1991
}