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]