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

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 $\text{O(}\text{n}\text{p}\text{+}\text{log log}\text{p)}$; (optimal for $\text{p ≤}\text{n}\text{log log}\text{n}$). 2. Merging two sorted lists of length m and n (m ≤ n) within a depth of $\text{O(}\text{n}\text{p}\text{+}\text{log}\text{n)}$ for p ≤ n (optimal for $\text{p ≤}\text{n}\text{log}\text{n}$), $\text{O(}\text{log}\text{m}\text{log}\text{p}\text{n}\text{)}$ for $\text{p ≥ n(= O(k)}\text{if}\text{p = m}{}^{\mathrm{<mtext>1</mtext><mtext>k</mtext>}}\text{n, k > 1)}$. 3. Sorting n elements within a depth of $\text{O(}\text{n}\text{p}\text{log}\text{n}\text{+}\text{log}\text{n}\text{log}\text{p)}$ for p ≤ n, (optimal for $\text{p ≤}\text{n}\text{log}\text{n}$). $\text{O(}\text{log}{}^2\text{n}\text{log}\text{p}\text{n}\text{) +}\text{log}\text{n)}$ for $\text{p ≥ n (= O(k}\text{log}\text{n)}\text{if}\text{p = n}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}\text{, k > 1)}$. The depth of O(klogn) for $\text{p = n}{}^{\mathrm{<mtext>1+</mtext><mtext>1</mtext><mtext>k</mtext>}}$ 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.