title: How to calculate or approximate the median of a list without storing the list
body: <p>I'm trying to calculate the median of a set of values, but I don't want to store all the values as that could blow memory requirements. Is there a way of calculating or approximating the median without storing and sorting all the individual values?</p>
  
  <p>Ideally I would like to write my code a bit like the following</p>
  
  <pre><code>var medianCalculator = new MedianCalculator();
  foreach (var value in SourceData)
  {
    medianCalculator.Add(value);
  }
  Console.WriteLine("The median is: {0}", medianCalculator.Median);
  </code></pre>
  
  <p>All I need is the actual MedianCalculator code!</p>
  
  <p><strong>Update:</strong> Some people have asked if the values I'm trying to calculate the median for have known properties. The answer is yes. One value is in 0.5 increments from about -25 to -0.5. The other is also in 0.5 increments from -120 to -60. I guess this means I can use some form of histogram for each value.</p>
  
  <p>Thanks</p>
  
  <p>Nick</p>