Is this better than the median scheme described in the


Another pivot selection scheme for parallel quicksort for hypercube (Section 9.17) is as follows. During the split along the i th dimension, 2i -1 pairs of processes exchange elements. The pivot is selected in two steps. In the first step, each of the 2i -1 pairs of processes compute the median of their combined sequences. In the second step, the median of the 2i -1 medians is computed. This median of medians becomes the pivot for the split along the i th communication link. Subsequent pivots are selected in the same way among the participating subcubes. Under what assumptions will this scheme yield good pivot selections? Is this better than the median scheme described in the text? Analyze the complexity of selecting the pivot.

Request for Solution File

Ask an Expert for Answer!!
Basic Computer Science: Is this better than the median scheme described in the
Reference No:- TGS01469162

Expected delivery within 24 Hours