With the following set of problems we will develop a divide and conquer based algorithm for the general problem of selection of an order statistics of an array.

The SELECT(A, k) problem asks to find the k smallest element of an array, i.e. an element x which will be at the kth position when A is sorted (or there are k -1 numbers in A smaller than x). More formally,

Input An array A of n distinct integers and an integer k.

Output A number x ∈ A, such that rank _A (x) = k.

This is a general problem in the sense that many order statistics or ordering problems can be solved with this.

Problem 1. Briefly, describe an algorithm to find the minimum, median, maximum of an array A using a subroutine for SELECT(A, k).

Problem 2. Briefly, describe an algorithm to sort an array A using a subroutine for SELECT(A, k).