Finding the maximum, merging, and sorting in a parallel computation model

Abstract

A model for synchronized parallel computation is described in which all p processors have access to a common memory. This model is used to solve the problems of finding the maximum, merging, and sorting by p processors. The main results are: 1. Finding the maximum of n elements (1 < p ≤ n) within a depth of O( n p + log logp); (optimal for p ≤ n log log n). 2. Merging two sorted lists of length m and n (m ≤ n) within a depth of O( n p + log n) for p ≤ n (optimal for p ≤ n log n), O( logm logp n) for p ≥ n(= O(k) if p = m 1 kn, k > 1). 3. Sorting n elements within a depth of O( n plogn + lognlogp) for p ≤ n, (optimal for p ≤ n log n). O( log2n logp n) + logn) for p ≥ n (= O(k logn) if p = n1+ 1 k, k > 1). The depth of O(klogn) for p = n1+ 1 k processors was also achieved by Hirschberg (Comm. ACM21, No. 8 1978, 657-661) and Preparata IEEE Trans ComputersC-27 (July 1978), 669-673). Our algorithm is substantially simpler. All the elementary operations including allocation of processors to their jobs are taken into account in deriving the depth complexity and not only comparisons. © 1981.