Parallel Sorting Flashcards
1
Q
How are the sample sort and the quick sort related?
A
Sample sort and quicksort are both comparison-based sorting algorithms. They are both divide and conquer algorithms and they also both use partitioning and pivots.
2
Q
Given a pivot in an array of numbers, how does one partition the array using multiple processors executing in parallel?
A
Divide the input array into equal-sized segments (or as close to equal as possible) based on the number of available processors. Assign each segment to a processor. Then create two local sub-arrays for elements greater and less than the pivot. Finally, execute a parallel prefix sum is performed on both arrays to get the final partitions.
