5. (20 pts extra credit) Recall that the MergeSort algorithm (Chapter 2.3 of CLRS) is a sorting algorithm that takes ?(n log n) time and ?(n) space. In this problem, you will implement and instrument MergeSort, then perform a numerical experiment that verifies this asymptotic analysis. There are two functions and one experiment to do this.

(i) MergeSort(A,n) takes as input an unordered array A, of length n, and returns both an in-place sorted version of A and a count t of the number of atomic operations performed by MergeSort.

(ii) randomArray(n) takes as input an integer n and returns an array A such that for each 0 ? i < n, A[i] is a uniformly random integer between 1 and n. (It is okay if A is a random permutation of the first n positive integers; see the end of Chapter 5.3.)

(a) From scratch, implement the functions MergeSort and randomArray. You may not use any library functions that make their implementation trivial. You may use a library function that implements a pseudorandom number generator in order to implement randomArray.

Submit a paragraph that explains how you instrumented MergeSort, i.e., explain which operations you counted and why these are the correct ones to count.

(b) For each of n = {24,25,...,219,230}, run MergeSort(randomArray(n),n) fives times and record the tuple (n, ?t?), where ?t? is the average number of operations your function counted over the five repetitions. Use whatever software you like to make a line plot of these 27 data points; overlay on your data a function of the form T(n) = An2, where you choose the constant A so that the function is close to your data.

Hint: To increase the aesthetics, use a log-log plot.