title: scala median implementation
body: <p>What's a fast implementation of median in scala?</p>
  
  <p>This is what I found on <a href="http://rosettacode.org/wiki/Averages/Median#Scala" rel="noreferrer">rosetta code</a>:</p>
  
  <pre><code>  def median(s: Seq[Double])  =
    {
      val (lower, upper) = s.sortWith(_&lt;_).splitAt(s.size / 2)
      if (s.size % 2 == 0) (lower.last + upper.head) / 2.0 else upper.head
    }
  </code></pre>
  
  <p>I don't like it because it does a sort. I know there are ways to compute the median in linear time.</p>
  
  <p><strong>EDIT:</strong></p>
  
  <p>I would like to have a set of median functions that I can use in various scenarios:</p>
  
  <ol>
  <li>fast, in place median computation that can be done in linear time</li>
  <li>median that works on a stream that you can traverse multiple times, but you can only keep <code>O(log n)</code> values in memory <a href="https://stackoverflow.com/questions/638030/how-to-calculate-or-approximate-the-median-of-a-list-without-storing-the-list">like this</a></li>
  <li>median that works on a stream, where you can hold at most <code>O(log n)</code> values in memory, and you can traverse the stream at most once (is this even possible?)</li>
  </ol>
  
  <p>Please only post code that <em>compiles</em> and <em>correctly computes the median</em>. For simplicity, you may assume that all inputs contain an odd number of values.</p>