A Logarithmic Time Sort for Linear Size Networks. Revised.
John H. Reif, Leslie Gabriel Valiant · Defense Technical Information Center (DTIC) · 1982
We give a randomized algorithm that sorts on an N node network with constant valence in O(log N) time. More particularly the algorithm sorts N items on an N code cube-connected cycles graph and for some constant k for all large enough alpha it terminates within K alpha log N time with probability at least 1-n/alpha.