[NathanRice]

That second question is kind of dirty. Pretty much all algorithms to find the median will perform a partial sort. Without any sorting at all, the only thing I can think of is some kind of statistical approximation based on sampling.

[pnathan]

Here's an interesting probabilistic way to sample up to the median: http://blog.aggregateknowledge.com/2013/09/16/sketch-of-the-...