title: Calculate the median of a billion numbers
body: <p>If you have one billion numbers and one hundred computers, what is the best way to locate the median of these numbers?</p>
  
  <p>One solution which I have is:</p>
  
  <ul>
  <li>Split the set equally among the computers.</li>
  <li>Sort them.</li>
  <li>Find the medians for each set.</li>
  <li>Sort the sets on medians.</li>
  <li>Merge two sets at a time from the lowest to the highest median.</li>
  </ul>
  
  <p>If we have <code>m1 &lt; m2 &lt; m3 ...</code> then first merge <code>Set1</code> and <code>Set2</code> and in the resulting set we can discard all the numbers lower than the median of <code>Set12</code> (merged). So at any point of time we have equal sized sets. By the way this cannot be done in a parallel manner. Any ideas?</p>