Given a set L with n elements, the kth order statistic of L is the kth smallest element of L. The minimum and maximum of a set are specific order statistics, where k = 1 and k = n, respectively.

The median is the middle element. There are two cases for the median, when n is odd, the median is at (n+1)/2. When n is even, there are two medians, one at n/2, and the other at (n/2) + 1.

Finding the kth smallest element in a list is called the selection problem. A simple way to solve the kth smallest problem is to sort the list and get the kth element. This will take O(n log n) time.

It is possible to solve the selection problem in O(n) time, as shown by Cormen et al in the reference. (If you feel industrious, node the algorithm below!)


Reference:
Cormen, Leiserson, Rivest, Introduction to Algorithms. Prentice-Hall, 1990. p. 185.

Log in or register to write something here or to contact authors.