%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 }