Linear-time Selection Algorithm, from an unsorted array, find the ith. item in sorted order, without actually sorting the array.

1.  Break up lists into groups of five.  Using brute force find the median of each group of 5.

2.  Using recursion (i.e. calling the whole algorithm) find the exact median of the medians computed above.

3.  Pivot the original array around this median of medians and then apply recursion to the correct set contained the desired element.

There is no need for recursion when the located element is in the equal list OR if it is in a before or after list of length 1.



Let's say we have a list of 100 elements and we want to find the 82nd. element.  What should we do?

Break it up into 20 lists of five items.

Find the median of each of these lists, using brute force.

I now have 20 elements.

I break the 20 elements into groups of five.

I have 4 groups of 5.  I find the median (brute force) of each of these groups of 5.

I now have a list of 4 items.

Brute force this for the median.

This median is NOT the pivot for the whole 100-element list.

This median is the pivot for the group of 20!!!

Only the EXACT median of the list of 20 can be used to partition the original list.  We use the median of 4 to help us find the exact median of the list of 20.