Sort the array A = <3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7> using the Quciksort

algorithm as given in the textbook (CLRS).

(a) Show what the array looks like after the PARTITION is called once.

(b) Tell whether the relative positions of any identical keys e.g., there are three 5s

are changed, after the PARTITION. You may want to mark the identical keys with

superscripts to differentiate them, e.g., 3^a , 1^a , 4, 1^b , 5^a , 9^a , 2, 6, 5^b , 3^b , 5^c , 8, 9^b , 7.

(c) Draw the recursion tree. In the tree, each node, corresponding to a call to the

PARTITION, has two boxes: one is filled with the input size for partitioning, and the

other is filled with number of comparisons done by the PARTITION.

(d) How many times is the PARTITION called?

(e) What is the depth of the recursion tree?

(f) How many comparisons are made?