Question

Briefly describe the parallel hyperquicksort algorithm on 8 cores. You can specify the pseudocode or describe in words. – 10 points.

Answer 1

In Hyper Quick-sort we want to sort an array A[n], of length =n ,parallely on a multi core system with 8 cores usiing Quick-sort.

Here we implement sequential algorithm ,while reducing the recursive function(/calls) by making parallel threads.

Algorithm:

-Sequential Quicksort is performed on local list in beginning of each process

-Pivot is choosen by choosing median of loacal list

-Next broadcasting of median value is done

-Next we divide them into : lower elements (low list) and greater elements(high list)

-To get a sorted local list , merge/combine the remaining local list with the received part (for each process)

-Do the same recusively for the uper and lower half processes