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 $=1$ ength$($m$)\frac{?}{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 $(1$eft$)$

right $=$ Mergesort $($right$)$

result $=$ Merge$(1$eft, right$)$

return result

The merge step is carried out by the following code:

Merge$(1$eft,right$)$

var list result

while length$(1$eft$)>0$ and length$($right$)>0$

if first$($left$)$ first$($right$)$

append first$($left$)$ to result

left $=$rest$(1$eft$)$

else

append first$($right$)$ to result

right $=$ rest $($right$)$

if length$(1$eft$)>0$

append rest$($left$)$ to result

if length$($right$)>0$

append rest$($right$)$ to result

return result

$6\mathrm{.}5\mathrm{.}1[10]$ $$6\mathrm{.}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 speedup

factor you might expect to obtain for values of $Y$ and length$($m$).$ Plot these on a

graph.

$6\mathrm{.}5\mathrm{.}2[10]$$$6\mathrm{.}2>$ Next, assume that $Y$ is equal to length $($m$).$ How would this

affect your conclusions your previous answer? If you were tasked with obtaining

the best speedup factor possible $($i$.$e$.,$ strong scaling$),$ explain how you might

change this code to obtain it$.$