Description
1. [14 marks] Consider Mergesort when n is not (necessarily) a power of 2. The method works
by (recursively) sorting a subarray of size n/2 and one of size n/2 and then merging them in
n-1 comparisons. A segment of length 1 requires 0 comparisons.
a. [2 marks] Give a recurrence relation that describes the number of comparisons used, in
the worst case, by this method.
b. [4 marks] Prove that n-1 comparisons are necessary (i.e. you cannot do it in fewer), in
the worst case for the merge step.
c. [4 marks] Prove that Mergesort, as described above, takes n lg n -2lg n
+1
comparisons in the worst case.
d. [4 marks] The expected number of comparisons for this method (over all possible
permutations of the input) is a little (Θ(n)) better. Prove it. (You do not have to deal
with the exact constant in this Θ(n) term.)
