1.
L.G. Valiant and J.H.
Reif, A Logarithmic Time Sort for Linear Size Networks. 15th Annual ACM
Symposium on Theory of Computing,
Boston, MA, April 1983, pp. 10-16.
[PDF]
Published in Journal of the ACM(JACM), Vol. 34, No. 1,
January 1987, pp. 60-76. [PDF]
2.
J.H. Reif, An n1+epsilon
Processor, 0(log n) Time Probabilistic Sorting Algorithm. SIAM 2nd
Conference on the Applications of Discrete Mathematics, Cambridge,
MA, June 1983, p. 27-29. [PDF]
3. S. Rajasekaran and J.H. Reif, An Optimal Parallel
Algorithm for Integer Sorting. 26th Annual IEEE Symposium on Foundations of
Computer Science, Portland, OR,
October 1985, pp. 496-503.
Published as Optimal and Sublogarithmic Time Randomized Parallel Sorting
Algorithms, SIAM Journal on Computing, Vol. 18, No. 3, June 1989, pp. 594-607. [PDF] or [PostScript] [PDF]
4. W.L. Hightower, J. Prins, and J.H. Reif,
Implementations of Randomized Sorting on Large Parallel Machines. 4th Annual
ACM Symposium on Parallel Algorithms and Architectures (SPAA'92), San Diego, CA, July 1992. [PDF]
5. S. Chen and J.H. Reif, Using Difficulty of
Prediction to Decrease Computation: Fast Sort, Priority Queue and Convex Hull
on Entropy Bounded Inputs, 34th Annual IEEE Conference on Foundations of
Computer Science (FOCS '93) Proceedings, November 1993, Palo Alto, CA, pp. 104-112. [PDF]