Exercise 7.4 Consider the following recursive mergesort algorithm (another classic divide and conquer algorithm). Mergesort was fi rst described by John von Neumann in 1945.

The basic idea is to divide an unsorted list x of m elements into two sublists of about half the size of the original list. Repeat this operation on each sublist, and continue until we have lists of size 1 in length. Then starting with sublists of length 1, “merge”

the two sublists into a single sorted list.

Mergesort(m)

var list left, right, result if length(m) ≤ 1 return m else var middle = length(m) / 2 for each x in m up to middle add x to left for each x in m after middle add x to right left = Mergesort(left)
right = Mergesort(right)
result = Merge(left, right)
return result The merge step is carried out by the following code:
Merge(left,right)
var list result while length(left) > 0 and length(right) > 0 if fi rst(left) ≤ fi rst(right)
append fi rst(left) to result left = rest(left)
else append fi rst(right) to result right = rest(right)
if length(left) > 0 append rest(left) to result if length(right) > 0 append rest(right) to result return result 7.4.1 [10] <7.2> Assume that you have Y cores on a multicore processor to run MergeSort. Assuming that Y is much smaller than length(m), express the speed-up factor you might expect to obtain for values of Y and length(m). Plot these on a graph.
7.4.2 [10] <7.2> Next, assume that Y is equal to length(m). How would this affect your conclusions in your previous answer? If you were tasked with obtaining the best speed-up factor possible (i.e., strong scaling), explain how you might change this code to obtain it.