Median of medians algorithm

1. If n is small, for example n<6, just sort and return the k'th smallest number.( Bound time- 7)
2. If n>5, then partition the numbers into groups of 5.(Bound time n/5). Sort the numbers within each group. Select the middle elements (the medians). (Bound time- 7n/5)
3. Call your "Selection" routine recursively to find the median of n/5 medians and call it m. (Bound time-Tn/5)
4. Compare all n-1 elements with the median of medians m and determine the sets L and R, where L contains all elements <m, and R contains all elements >m. Clearly, the rank of m is r=|L|+1 (|L| is the size or cardinality of L). (Bound time- n)
5. If k=r, then return m
6. If k<r, then return k th smallest of the set L .(Bound time T 7n/10)
7. If k>r, then return k-r th smallest of the set R.

Source: ranger.uta.edu/~gdas/Courses/Fall2004/.../W6Presentation.ppt


This algorithm (O(n)) is used to improve the worst case performance of basic (partitioning) order selection algo used in quicksort (O(n^2)) .