1.
Leslie G.
Valiant and John 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.
John H. Reif,
An n^{1+epsilon} Processor, 0(log n) Time Probabilistic Sorting
Algorithm. *SIAM 2nd Conference on the
Applications of Discrete Mathematics*,*
*Cambridge, MA, June 1983, pp. 27-29. [PDF]

3. Sanguthevar Rajasekaran and John 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 John H. Reif, Implementations of Randomized Sorting on Large Parallel
Machines. *4th Annual ACM Symposium on
Parallel Algorithms and Architectures (SPAA'92)*, San Diego, CA, pp. 158-167,
July 1992. [PDF]

5. Sefeng Chen and John 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]