This week's algorithm design and analysis will be on a topic called Order Statistics. The ith order statistic of a set of n elements is the ith smallest element. We can find the first and nth order statistic (min and max) easily in O(n) time by doing an algorithm like this:

let min <- A[1] for i = 2 to A.length if min > A[i] let min <- A[i] return min

And a similar idea for maximum. However, what I want to know is given an unsorted array A[1...n], can we find any ith order statistic also in O(n)? If so, give an algorithm and prove your statement.

For example, if I gave you A = [4,1,2,7,5] and asked for the 3rd order statistic, I would return 4

Hint: You can't just sort it and return the ith element

Please put your psuedocode in [spoiler ] tags and I'll post the right answer in a week.