The implementation of a simple but efficient randomized algorithm
for finding the ith order statistic, using divide and conquer.
Definition 1. The ith order statistic of an array A of n numbers is (1) the ith smallest number
in A, if i n; or (2) not defined, otherwise.
Note that the given array A is arbitrary and may not be sorted. Also, array A may or may not
have duplicates in its member elements. Below are a few examples:
The first order statistic of A[5, 4, 2, 7] is 2, because 2 the smallest number in the array A.
Obviously the first order statistic is just the minimum of all the array elements.
The nth order statistic of an array A[0..n 1] is just the maximum of all the array elements.
Both the third and the fourth order statistics of A[5, 2, 4, 7, 4, 1] are the number 4, because 4
the third as well as the fourth smallest number in the array A.
The seventh order statistic of A[5, 2, 4, 7, 4, 1] does not exist, because array A has only 6
numbers.