Originally Posted by
TriKri This is an algorithm to find the median number of a sequence of numbers, it works in linear time in average case: Quickselect. (It can even find the n:th smallest element)
But I think this algorithm works in linear time in all cases: BFPRT. But that depends on the Median of Medians algorithm. If the Median of Medians algorithm does find a number that is guaranteed to be greater than or equal to at least X % of the numbers and smaller than or equal to at least X % of the numbers, where X is a constant, then the BFPRT algorithm does work in linear time in worst case, I believe. But what is X and how can you show that? (Then it even works in liear time in worst case when it is going to find the n:th smallest element)