Publications [#236905] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Reif, JH; Valiant, LG, A logarithmic time sort for linear size networks, Journal of the ACM Jacm, vol. 34 no. 1 (January, 1987), pp. 60-76, Association for Computing Machinery (ACM) [doi]
   (last updated on 2026/01/14)

   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 α, it terminates within kα log N time with probability at least 1 - N-α. © 1987, ACM. All rights reserved.