I'd cheat in a slightly different way. If the data are employee ages, you know that they are probably integers[0] and certainly bounded between 0 and 128. Bi

I'd cheat in a slightly different way. If the data are employee ages, you know that they are probably integers[0] and certainly bounded between 0 and 128. Bin the ages into years and accumulate the per-year and total counts, which is a snap: O(N) time, O(1) space, and trivial to parallelize. Find the bin where the cumulative sum is equal to half the total counts and you're done. [0] Even if they're not integers, you probably don't need ages more granular than a day, which is still a manageable number of bins (~50k).