## 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.)