A logarithmic time sort for linear size networks
John H. Reif, Leslie Gabriel Valiant · Journal of the ACM · 1987
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 - α .