MODIFIED QUICKSORT Consider the modification of the determin

MODIFIED QUICKSORT

Consider the modification of the deterministic quicksort algorithm described in class so that, instead of selecting the first element in an nn-element sequence as the pivot, we choose the element at index n/2n/2, that is, an element in the middle of the sequence.

(a) What is the running time of this version of quicksort on a sequence that is already sorted? Use O-notation; you do not need to explain your answer.

(b) Describe an input sequence that would cause this version of quick-sort to run in (n2)(n2) time.

Solution

a)

Picking the middle element of a sorted array as the pivot results in a balanced split. So the running time satisfies

the recursion T(n) = 2T(n/2) + n 1. This is the same recursion as for merge-sort, which has running time n

log n n + 1 or (n log n).

b)

For an input of size 8, use 8, 6, 4, 2, 1, 3, 5, 7 or 1, 3, 5, 7, 8, 6, 4, 2 or 4, 3, 2, 1, 8, 7, 6, 5 or 6, 4, 7, 1, 8, 2, 3, 5,

etc. The pattern should be that, at any point, the middle element, which is the one being removed, is the smallest

largest number of the current array.