The kth quantiles of an n-element set A are the k 1 order statistics that divide the sorted set into k equal-sized sets (to within 1). That is, the kth quantiles are Select(A, n/k), Select(A, 2n/k), , Select(A, (k 1)n/k) (here we are assuming that k divides n). Finding the kth quantiles directly in this way would take O(nk) time. Given an unsorted array A of n distinct keys and an integer k, with 1 k n, give an O(nlogk) algorithm to find the kth quantiles of A. You may assume that k divides n. You may assume that the linear-time (deterministic) Select algorithm (page 220) is available as a subroutine.

1. Describe your algorithm in pseudocode. Comment your code.

2. Prove that your algorithm is correct, i.e., argue that it returns the kth quantiles of A. Use induction.

3. Analyze the running time of your algorithm, i.e., explain carefully why your code runs in O(nlogk) time.