HW2, Written Part

Due July 17

30 Points

Objectives: understanding mergesort and quicksort

Problem 1: MergeSort

Part A [5 points]: Show how mergesort sorts the following input:

3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5

Part B [3 points]: Determine the running time of mergesort on the following inputs.

1. Sorted Increasing

2. Sorted Decreasing – (Reverse-ordered)

3. Random

Problem 2: QuickSort

Part A [5 points]:

Assume that the pivot element in quicksort is always chosen to be the middle element in the array. What is the worst case running time of quicksort with this pivot choice. Given an example with 11 elements that cause this worst case behavior.

Part B [5 points]:

One deterministic improvement to quicksort is as follows: to choose the pivot we pick three poissible candidates. The first one, the last one and the middle one in the array, then we set the pivot to the median of these three elements and then partition. Give an example with 11 elements that cause this worst case behavior.

Part C [12 points]:

In class we have seen a quicksort implementation which picks the pivot as the median of a[left], a[center], a[right] by sorting them and then swaps a[center] with a[right-1]. The partitioning loop can then start with i = left+1 and j = right-2, with the pivot residing in a[right-1]. One advantage of such an implementation is that the partitioning loop will not run out of bounds because j will stop when it gets to a[left] and i will stop when it gets to a[right] (see the code in the book or on the class website if this is not making sense to you :) ). However, another advantage is that this implementation yields more balanced partitions in certain cases.

Consider an implementation of quicksort which picks the pivot as the median of a[left], a[center], and a[right] (without sorting them) and then swaps it with a[right]. The partitioning loop then starts with i = left and j = right-1. What is the runtime of this version when the input is 2,3,4,...,N-1,N,1? Justify your answer (Hint: do one iteration and compare the sizes the two subarrays and see if this behavior will be repeated in the next iteration).