Week 6: Exercises

1. Merge Sort Visualization

Modify our merge sort implementation from the lecture so that it prints out each subarray as it sorts it recursively. Use indentation to show the hierarchical structure of the recursive calls. For example:

>>> a = [5, 2, 6, 8, 10, 1, 3, 17, 14, 4, 9]
>>> mergesort(a)
[5, 2, 6, 8, 10, 1, 3, 17, 14, 4, 9]
  [5, 2, 6, 8, 10]
    [5, 2]
      [5]
      [2]
    [6, 8, 10]
      [6]
      [8, 10]
        [8]
        [10]
  [1, 3, 17, 14, 4, 9]
    [1, 3, 17]
      [1]
      [3, 17]
        [3]
        [17]
    [14, 4, 9]
      [14]
      [4, 9]
        [4]
        [9]

2. Merge Sort Writes

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?

3. Merge Sort Memory

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?

4. Running Time

Consider this function:

def foo(n):
    if n == 0:
        return 0
    
    return foo(n // 2) + foo(n // 2)

a) For a given n, what value will the function compute?

b) Write down a recurrence for T(N), the time to run the function foo(N).

c) Solve the recurrence. Hint: Expand it into a tree as we did when we solved the recurrence for mergesort.

d) Suppose that we change the last line to

return 2 * foo(n // 2)

Clearly this will not change the value that the function computes. Will this modification change its big-O running time?

5. Average Partition Size

In quicksort, suppose that use Hoare partitioning and 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.

6. Incomplete Partitioning

Consider the Hoare partitioning function for quicksort that we saw in the lecture:

def partition(a, lo, hi):
    p = a[randrange(lo + 1, hi)]  # choose random pivot  

    i = lo
    j = hi - 1

    while True:
        # Look for two elements to swap.
        while a[i] < p:
            i += 1
        while a[j] > p:
            j -= 1

        if j <= i:             # nothing to swap
            return i
        
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

Suppose that we remove the last two lines from the function above. Show that the function will no longer behave correctly with this change. Specifically, give an example of an input array on which the function will fail.