In a classic paper Munro and Paterson study the problem of how much storage is required for an algorithm to find the median in a randomly sorted array.  In particular they focus on the following model:the input is read from left to right for a number P of times.It is shown that $O(n^{\frac{1}{2P}})$ memory cells are sufficient, but the corresponding lower bound is only known for P=1.  I haven't seen any result for P>1.  Is anyone aware of such lower bounds?  Notice that the main difficulty here is that at the second pass the input is not randomly ordered anymore.
Storage requirements for median selection (two passes algorithms)
ds.algorithms;space bounded;data streams
Try this paper by Chan in a recent SODA: http://portal.acm.org/citation.cfm?id=1721842&dl=ACM .A quick Google search also found the following paper that looks possibly relevant, but I haven't read it: http://portal.acm.org/citation.cfm?id=1374470 .