Analyze mergesort for the case when n is not a power of 2. Partial solution. When n is an odd number, one subarray has one more element than the other, so when n is not a power of 2, the subarrays on...

Analyze mergesort for the case when n is not a power of 2.

Partial solution. When n is an odd number, one subarray has one more element than the other, so when n is not a power of 2, the subarrays on each level are not necessarily all the same size. Still, every element appears in some subarray, and the number of levels is still logarithmic, so the linearithmic hypothesis is justified for all n.

The following exercises are intended to give you experience in developing fast solutions to typical problems. Think about using binary search and merge sort, or devising your own divide-and-conquer algorithm. Implement and test your algorithm.