Is it possible to calculate median of a list of numbers better than O(n log n)?

Question

I know that it is possible to calculate the mean of a list of numbers in O(n). But what about the median? Is there any better algorithm than sort (O(n log n)) and lookup middle element (or mean of two middle elements if an even number of items in list)?

Answer 1

Yes. You can do it (deterministically) in O(n).