Publications [#236927] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Rajasekaran, S; Reif, JH, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, vol. 18 no. 3 (January, 1989), pp. 594-607, Society for Industrial & Applied Mathematics (SIAM) [doi]
   (last updated on 2026/01/14)

   Abstract:
   This paper assumes a parallel RAM (random access machine) model which allows both concurrent reads and concurrent writes of a global memory. The main result is an optimal randomized parallel algorithm for INTEGER-SORT (i.e., for sorting n integers in the range [1, n]). This algorithm costs only logarithmic time and is the first known that is optimal: the product of its time and processor bounds is upper bounded by a linear function of the input size. Also given is a deterministic sublogarithmic time algorithm for prefix sum. In addition this paper presents a sublogarithmic time algorithm for obtaining a random permutation of n elements in parallel. And finally, sublogarithmic time algorithms for GENERAL-SORT and INTEGER-SORT are presented. Our sublogarithmic GENERAL-SORT algorithm is also optimal.