Suppose that we run merge sort on an array that contains N elements. (If you like, you may assume that N is a power of 2.)
a) How many times will each array element be copied to a different memory location during the course of the sort?
b) How many array writes will the sort perform in all?
c) Does the running time of merge sort depend on the initial arrangement of the values that are being sorted? In particular, is it more efficient when run on an input array that is already sorted?
Consider the merge sort implementation that we saw in the lecture.
a) If we use it to sort an array that occupies N bytes of memory, what is the largest amount of additional memory that will be required at any moment during the sorting process? (Assume that any temporary arrays are freed as soon as there are no more references to them.)
b) Is it possible to modify our implementation to reduce this memory requirement?
In quicksort, suppose that we choose pivot elements randomly. In each partition operation, let f be the size of the smaller partition, as a fraction of the number of elements being partitioned in that step. What value do you think f will have, on average? Perform experiments to determine whether your intuition is correct.
Perform experiments to answer these questions:
a) If we choose random pivot elements in a quicksort implementation, how much of the overall running time is spent in choosing these elements? In other words, how expensive is this random selection process?
b) What is the relative running time of merge sort and quicksort on randomly permuted input data? Does this relative running time change as the input size increases?