Designing a parallel algorithm to find the second largest item in an array

Question

Using pseudocode, I need to design a parallel algorithm that, when given k keys, a[0], a[1], a[2],... a[k-1] stored in an unsorted array a, would find the second largest key in it.

I'm new to parallel computing, so I know that in terms of sequential programming, we can use bubble sort with two passes. First pass gets your the largest element, while the second pass will get you the second largest element, the goal. Should we split the bubble sorta via parallel processing, we only need to do one pass each iterations largest element to find the second largest. My problem is I don't know how to exactly 'parallelize' the algorithm.

Answer 1

I'll sketch informally one obvious variant, assuming some model with shared memory and unbounded parallelism (I'm not going to discuss the synchronization issues, though). Lets denote the size of the original array as $n$.

1. Divide your array into $k$ subarrays of approximately equal sizes $s_i$, such that $s_i \approx \frac{n}{k} \wedge s_i \ge 2$, then assign each subarray to a thread or whatever you use, lets call it "process". This assignment procedure can be (should be) implemented in a way such that its time complexity is $O(1)$.
2. Then $i$-th parallel process finds the largest $M_i$ and the second largest element $m_i$ of $i$-th subarray sequentially. It's an easy linear complexity algorithm, which works in one go through all the elements of the input. So, time complexity of this step is $O\left(\frac{n}{k}\right)$. $i$-th process will store the results in the first two elements of $i$-th subarray, so you won't need to send $M_i$ and $m_i$ anywhere and resolve the synchronization issues connected with sending/receiving. That's why we need $s_i \ge 2$, and if there is not enough elements then it is not worth to process it in parallel.
3. Wait until all processes finish (its called a barrier). At this point you have an array of all the results ($M_i$ and $m_i$) of all processes. Now, simply use the sequential algorithm again. The resulting $m$ will be the answer for the whole original array. Time complexity of this step is $O(k)$.

The overall time complexity of our algorithm is $O\left(\frac{n}{k} + k\right)$. Under this very simplistic model it's better to have the number of parallel processes $k \sim \sqrt{n}$ to make the overall time complexity minimal: $O \left( \sqrt{n} \right)$. This result can be easily obtained using differential calculus. Of course, this result is very far from the reality of practical parallel computing: we don't have unbounded parallelism in practice and we need to consider the parallel processing management overhead.