SELECTION:

Input: A list of numbers S; an integer k

Output: The kth smallest element of S

For instance, if k = 1, the minimum of S is sought, whereas if k = ceiling(|S|/2), it is the median.

Develop a divide-and-conquer approach to selection. Hint: for any number v, imagine splitting list S into three categories: elements smaller than v, those equal to v (there might be duplicates), and those greater than v.

In your answer, show the following:

1. Briefly describe the divide, conquer, and combine steps;
2. Clearly define the recursive function for selection(S, k); (note: this is not the function for the time complexity of the selection function.)
3. Analyze the best case and worst case time complexity of this approach given input size n.