Papers by Reif on Sequential and Parallel Sorting (5 papers)


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 n1+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]