How to find the median (or approximate median) of n chunks of values. The values in each chunk can be assumed to have been sorted if it helps. In addition, the existence of a histogram for each chunk is allowed.

  • 4
    $\begingroup$ Reading your question literally, the answer is: ignore the subsetting of your data into chunks, and simply take the median of the entire pooled dataset. Perhaps I am misunderstanding the question. Can you not simply take the median of the set of all values in your dataset? Why does it matter that the data are in "chunks"? Is there some part of this structure that you hope to preserve? $\endgroup$ Dec 18, 2012 at 3:45
  • $\begingroup$ Are you saying that your values are somehow aggregated? In what format are your data? $\endgroup$
    – AdamO
    Apr 17, 2013 at 18:06

1 Answer 1


I first assume you do not have the possibility to save all chunks and just compute the median from all values. If you do but the values are un ordered I would recommend a selection algorithm to find the median, see Selection algorithm (wikipedia).

I also assume that the chunks don't contain elements in some sequential order such that the smallest elements come in one chunk and then the larger in the next etc. At which case you only need to find the median in the middle chunk.

I think you're looking for some kind of recursive estimator of the median but to find a good estimator for this is hard. I would recommend to use some kind of frequency count which you update for each new chunk of data giving you the possibility to get the median using these counts. Depending on the amount of possible values this might become unfeasible in terms of space. But depending on the data structure used you should be able to do this for most cases.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.