%0 Conference Paper %1 reif83 %A Reif, John H. %A Valiant, Leslie G. %B Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing %C New York, NY, USA %D 1983 %I ACM %K algorithm sorting sorting.network %P 10--16 %R 10.1145/800061.808727 %T A Logarithmic Time Sort for Linear Size Networks %X We give a randomized algorithm that sorts on an N node network with constant valence in 0(log N) time. 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;. %@ 0-89791-099-0

@inproceedings{reif83, abstract = {We give a randomized algorithm that sorts on an N node network with constant valence in 0(log N) time. 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 = {808727}, added-at = {2016-10-29T05:06:34.000+0200}, address = {New York, NY, USA}, author = {Reif, John H. and Valiant, Leslie G.}, biburl = {https://www.bibsonomy.org/bibtex/2e59f16a2cde117f1232ff52b96f127d4/ytyoun}, booktitle = {Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing}, doi = {10.1145/800061.808727}, interhash = {28d134a53f6a127253045aeb7f1b9a59}, intrahash = {e59f16a2cde117f1232ff52b96f127d4}, isbn = {0-89791-099-0}, keywords = {algorithm sorting sorting.network}, numpages = {7}, pages = {10--16}, publisher = {ACM}, series = {STOC '83}, timestamp = {2016-10-29T12:10:51.000+0200}, title = {A Logarithmic Time Sort for Linear Size Networks}, year = 1983 }