Question

Write a PRAM algorithm for Quicksort using \(n\) processors to sort a list of \(n\) elements.

Short answer

A PRAM Quicksort algorithm involves the selection of a pivot element, the parallel division of the array elements into groups ('low' and 'high'), and the parallel calculation of prefix sums to decide where elements will be placed after partitioning. Both 'low' and 'high' sublists are then recursively sorted in parallel, after which, they are combined in the correct order to produce the sorted list as output.

Step-by-step solution

Initialize Input Array

Start by initializing an unsorted array with n elements that needs to be sorted.

Pivot Selection

Choose the pivot element. This could be the first, the last, the median, or any random element. Its choice doesn't affect the parallelization but can affect the speed of the algorithm.

Split into Groups

Split the array into two groups, with one processor assigned to each element of the array. Each processor compares its element with the pivot: if it's less than or equal to the pivot, it puts its element into the 'low' group; if it's greater, it goes into the 'high' group.

Calculate Prefix Sums

To find out where to put their elements in the new array, processors calculate prefix sums on a boolean vector where 1 indicates a 'low' element and 0 indicates a 'high' element. The prefix sum of an element gives the new position for a 'low' element, and for a 'high' element, it's found by subtracting the prefix sum from the total number of 'low' elements.

Perform Write

Each processor now knows where to write its element, so it performs the write, creating a new array that has 'low' elements followed by 'high' elements.

Quicksort Sublists

Recursively apply Quicksort to each of the 'low' and 'high' sublists using a divide-and-conquer approach. If a sublist has more than one element, use the PRAM Quicksort algorithm on that sublist. If a sublist has one element, no need to sort it.

Combine Results

After the recursive Quicksort calls are finished, combine the sorted 'low' and 'high' sublists into a single sorted list. Since the 'low' and 'high' sublists are already in the correct order relative to each other (all 'low' elements are less than or equal to all 'high' elements), no merging is needed. We just concatenate the 'low' sublist in front of the 'high' sublist.