People had the most difficulty with Problem 7.  It was
intended to be one of the more difficult problems, but
it was a direct application of what we learned about
mergesort.

====
7. (14 points total)  Consider the following modification
to mergesort, called 4-way mergesort.  Instead of dividing
the input array into two subarrays, 4-way mergesort divides
the array into four subarrays (as equally-sized as possible),
sorts them recursively, and then calls a 4-way merge
function, which combines four sorted arrays into one
sorted array.

a. (2 points)  What is the worst case number of comparisons
4-way merge makes if given as input four arrays, each of
size M?  Do not use Big-Oh notation.

b. (4 points)  Write a recurrence relation T(N) that
expresses the worst case number of comparisons used in
4-way mergesort given an array of N elements as input.
(We can assume that T(1) = 1.)  Do not use Big-Oh notation.

c. (4 points)  Solve the recurrence relation.  Show your
work (either on this page or on the back of the previous
page — if you use the previous page, indicate you did so).

d. (4 points)  For large input sizes (but small enough
to fit in main memory), do you think 4-way mergesort
would run faster in practice than normal (2-way)
mergesort?  Why or why not?
====

This question asks you to go through an analysis that
is similar to the analysis of normal (2-way) mergesort.
It's difficult (if not impossible) to answer these
questions without understanding the analysis of
mergesort.


a. Recall how 2-way merge works.  We have an index
for each of the two sorted subarrays.  We compare
the elements they are pointing to, and the smaller
one gets put into the output array (and its index
is advanced).  In the worst case, if we have two
M-element arrays to merge, this will take 2M-1
comparisons.

Similarly, if we have four M-element sorted arrays
to merge, then there is a very similar idea.  We
have an index for each of the four arrays.  It takes
three comparisons to determine the smallest of the
four.  In the worst case, we must do this until each
list has only one element left.  That means it takes
3*4*(M-1) comparisons.  But then it takes 3 + 2 + 1
more comparisons to finish off the remaining four
elements.  So, the total number of comparisons is
12M - 6.

There's actually a way to do this that requires
fewer comparisons.  If A, B, C, and D are the four
arrays, we can merge A and B to form a sorted array
of size 2M in 2M-1 comparisons, and then merge
C and D to form another sorted array of size 2M in 2M-1
comparisons. Then, we merge the two arrays (each of
size 2M).  This takes 4M-1 comparisons.  The total
number of comparisons is 8M-3.  For the rest of this
problem, let's use the 8M-3 result.


b. 4-way mergesort breaks the problem of sorting N
numbers into 4 problems of sorting N/4 numbers and
then requires 2N - 3 comparisons (since N = 4M) to
merge the four sorted arrays.  So, the recurrence
relation for 4-way mergesort is:
  T(N) = 4 T(N/4) + 2N - 3

(or, T(N) = 4 T(N/4) + 3N - 6 if you had 12M-6 for
part a.)


c. We can solve the recurrence relation in almost
exactly the same way as 2-way mergesort.

Brute force:
T(N) = 4 T(N/4) + 2N    (throw away the "-3")
     = 4 (4 T(N/16) + 2N/4) + 2N
     = 16 T(N/16) + 2N + 2N
     = ...
     = 4^k T(N/(4^k)) + k(2N)
(Let k = log_4 N, where "log_4" means logarithm base 4.)
     = N T(1) + (log_4 N) (2N)
     = 2N log_4 N + N

Telescoping:
T(N) = 4 T(N/4) + 2N    (throw away the "-3")
T(N)/N       = T(N/4)/(N/4) + 2
T(N/4)/(N/4) = T(N/16)/(N/16) + 2
T(N/16)/(N/164) = T(N/2516)/(N/256) + 2
...
T(4)/4 = T(1)/1 + 2

Adding up both sides of the equations, we get

T(N)/N = T(1)/1 + 2 log_4 N
T(N) = N + 2N log_4 N


Note that log_4 N = (log_2 N) / (log_2 4),
so 2N log_4 N = N log_2 N.


d. You cannot have an intelligent opinion for this part
unless you successfully completed part c, because
whether or not 4-way mergesort is faster than 2-way
mergesort has something to do with how many comparisons
each makes.

So let's compare:
# of comparisons for 4-way mergesort: N log_2 N + N
# of comparisons for 2-way mergesort: N log_2 N + N

They are the same.  We can't quite conclude that they
would run just as fast as each other in practice,
because we have to consider how much work each algorithm
does for each comparison.  In other words, we need
to think about the constant factor that is associated
with each comparison.

It turns out that 4-way mergesort will be a little
more complicated, because the merge routine has more
overhead associated with keeping track of four indexes
and checking for when the indexes reach the end of their
array.

So, although the number of comparisons are the same,
4-way mergesort would run a little slower than 2-way
mergesort.

(Note that if you calculated 12M -6 for part a, then
T(N) = (3/2)N log_2 N + N, and such an implementation
of 4-way mergesort would be much slower than 2-way
mergesort.)