Select in linear time

Return the value that would be at position k if values were sorted, with 0 <= k < n. Use median of medians to choose pivots, so that the method is O(n) even on the worst lists.

select([7, 2, 9, 4, 1], 2)     # 4
select([5, 1, 5, 1, 5, 3], 3)  # 5

The tests pass the larger lists' values as special number objects that count every comparison made with them (<, <=, >, >=; == is not counted). They behave like normal numbers, and max() and min() count too. Return the values you were given, not copies made with int().

• On every list, your method may make at most 20n comparisons.
• The comparisons per value must stay flat as the list grows: for a list 32 times longer, at most 25% more per value. Sorting fails this, because it makes about log₂ n comparisons per value.

sorted(), .sort(), heapq and the functions of random are switched off. Lists of 5 values or fewer can be sorted by hand (insertion sort).

Limits

• Up to 64,000 values. Lists may be sorted, reversed, all equal, or built to beat a simple pivot rule.