%0 Journal Article %1 reif87 %A Reif, John H. %A Valiant, Leslie G. %C New York, NY, USA %D 1987 %I ACM %J J. ACM %K algorithm sorting sorting.network %N 1 %P 60--76 %R 10.1145/7531.7532 %T A Logarithmic Time Sort for Linear Size Networks %V 34 %X A randomized algorithm that sorts on an N node network with constant valence in O(log N) time is given. More particularly, the algorithm sorts N items on an N-node cube-connected cycles graph, and, for some constant k, for all large enough &agr;, it terminates within k&agr; log N time with probability at least 1 - N-&agr;.

@article{reif87, abstract = {A randomized algorithm that sorts on an N node network with constant valence in O(log N) time is given. More particularly, the algorithm sorts N items on an N-node cube-connected cycles graph, and, for some constant k, for all large enough &agr;, it terminates within k&agr; log N time with probability at least 1 - N-&agr;.}, acmid = {7532}, added-at = {2016-10-29T05:07:08.000+0200}, address = {New York, NY, USA}, author = {Reif, John H. and Valiant, Leslie G.}, biburl = {https://www.bibsonomy.org/bibtex/2ad4a7e2c153015477e0179800e93f310/ytyoun}, doi = {10.1145/7531.7532}, interhash = {2ff9d78ddd8fbef9225a8e06962cfd8c}, intrahash = {ad4a7e2c153015477e0179800e93f310}, issn = {0004-5411}, issue_date = {Jan. 1987}, journal = {J. ACM}, keywords = {algorithm sorting sorting.network}, month = jan, number = 1, numpages = {17}, pages = {60--76}, publisher = {ACM}, timestamp = {2016-10-29T12:10:19.000+0200}, title = {A Logarithmic Time Sort for Linear Size Networks}, volume = 34, year = 1987 }