Median of 10 Billion Integers

It's Friday afternoon. Maya gets handed 50 files.

"We need the median of all of it. Before Monday." Maya looks at the disk: 50 files, 10 billion 32-bit integers in total — about 40 gigabytes of raw data. Her laptop has 16 GB of RAM. The math is unkind.

The first instinct of every engineer who has ever passed a coding interview is the same: just sort it and pick the middle one. That instinct is correct on a whiteboard with 7 numbers. It is catastrophically wrong with 10 billion. The whole point of this article is to show you why it's wrong, and what the right shape of the answer looks like — without any black magic, just one simple idea applied twice.

Before we touch a line of code, let's get the units straight. They will matter for every decision we make later.

"Just sort it" — and the wall it runs into

Maya's first attempt looks like every textbook answer: load the data, sort it, return arr[N/2]. Watch what happens at each step.

Right. So we don't load it all. The next-best textbook answer is external merge sort — break the input into RAM-sized chunks, sort each chunk, write each sorted chunk back to disk, then merge them all into one giant sorted file. This is a real algorithm; databases use it. Let's count what it costs us.

This is the trap: external merge sort produces an artifact (a fully sorted file) that is far more powerful than the question asked for. We don't need every element in order. We need one element — the one at rank N/2. Paying to sort all 9,999,999,999 of the others is wasted work.

You don't need order. You need rank.

Here is the single insight that unlocks everything: the median is defined purely by its position in the sorted list, not by the sort itself. You only need to find the value v such that exactly N/2 values in the dataset are ≤ v. You don't need to know what's to the left of it. You don't need to know what's to the right of it. You just need to know where the boundary sits.

Think of it like this analogy. Imagine you ask 10 billion people their height and want to find the median height. You don't need to line them all up in a row. You can just ask each person to step into the room labeled with their height-bracket — under 150 cm, 150–160, 160–170, and so on. Then you walk the rooms in order and count: "room 1 has 1.8 billion, room 2 has 2.0 billion, room 3 has 2.5 billion — that's 6.3 billion, we've crossed the halfway mark of 5 billion in room 3, the median is somewhere in this room."

You never sorted anyone. You just counted who landed where. That's the entire trick.

Buckets — voting boxes for numbers

A 32-bit signed integer has a fixed, finite range: from −2³¹ (about −2.15 billion) to 2³¹ − 1 (about +2.15 billion). That's roughly 4.3 billion possible distinct values. Bounded range is the magic word — it means we can pre-define a fixed grid of buckets that covers every possible value, no surprises.

Here is the picture. Carve up the entire integer range into 2¹⁶ = 65,536 equal-sized buckets. Each bucket is just a counter — an entry in an array. When we read a number v from disk, we figure out which bucket it belongs to, and increment that counter. That's it. We never store v itself.

Why "high 16 bits"?

A 32-bit integer is just two halves stitched together: 16 high bits and 16 low bits. The high bits tell you the coarse position of the number (which broad bracket it's in); the low bits tell you the fine position within that bracket. If you split the value range into 65,536 equally-sized buckets, then which bucket a number falls into is determined entirely by its high 16 bits.

The bucket index is just one CPU instruction:

// for unsigned thinking; we'll handle signed offset in a moment
int idx = (v >>> 16) & 0xFFFF;   // high 16 bits, value in [0, 65535]
buckets[idx]++;

Coarse histogram — find the bracket

Pass 1 is a single sequential read of all 50 files. For every integer v we see, we increment buckets[high16(v)]. At the end of the pass, the array tells us how the 10 billion values are distributed across 65,536 brackets.

Now we go hunting for the median. We walk the buckets in order, keeping a running sum. The moment that sum first reaches N/2, the bucket we just stepped into is the one that contains the median.

long target = N / 2;
long cumulative = 0;
int medianBucket = -1;
long countBefore = 0;

for (int i = 0; i < 65536; i++) {
  if (cumulative + buckets[i] >= target) {
    medianBucket = i;
    countBefore = cumulative;        // values strictly before this bucket
    break;
  }
  cumulative += buckets[i];
}

Two things come out of this loop, and we'll use both in Pass 2:

What about negative numbers?

A small detail that trips people up. With signed 32-bit ints, the bit pattern 0x80000000 is the most-negative number, and 0x7FFFFFFF is the most-positive. If you bucket by raw high-16-bits, the negatives land at the top of the array, not the bottom — which would silently break the "walk in order" loop above.

The fix is a one-liner at read time: add 2³¹ to every value (or equivalently, XOR the sign bit). That maps the signed range [−2³¹, 2³¹−1] to the unsigned range [0, 2³²−1], preserving order. Now bucket index 0 holds the most negative numbers, bucket 65,535 holds the most positive, and the cumulative walk works correctly. We undo the offset only at the very end when we report the answer.

Zoom in — find the exact value

Pass 1 narrowed the median to one of 65,536 brackets. Each bracket is 2¹⁶ = 65,536 values wide. We now do the same trick again — but this time we only care about values that land in medianBucket, and we sub-bucket them by their low 16 bits.

It's the same algorithm, scoped down. We allocate another 65,536-entry counter array (sub[]). We re-stream all 50 files. For each integer, we filter — if its high 16 bits don't match medianBucket, we ignore it. Otherwise, we extract its low 16 bits and increment sub[low16(v)].

long[] sub = new long[65536];

for (int v : streamAllFiles()) {
  int hi = (v >>> 16) & 0xFFFF;
  if (hi == medianBucket) {
    int lo = v & 0xFFFF;
    sub[lo]++;
  }
}

After Pass 2, sub[] tells us how many copies of every individual value in medianBucket exist in the dataset. We do one last cumulative walk:

long needRank = target - countBefore;   // rank within medianBucket
long cum = 0;
int medianLow = -1;

for (int i = 0; i < 65536; i++) {
  cum += sub[i];
  if (cum >= needRank) { medianLow = i; break; }
}

int median = (medianBucket << 16) | medianLow;   // stitch back together

Two 16-bit halves combine to give the exact 32-bit median value. Done — in two sequential reads of the data, with under 1 MB of RAM total.

Tiny numbers, full trace

Algorithms feel abstract until you watch them eat real numbers. Let's shrink the problem so the whole thing fits on a screen.

Pretend our integers are 4 bits wide (range [0, 15]) and we have N = 16 of them across two files. We'll use 4 buckets in each pass instead of 65,536, but the math is identical.

Pass 1 — coarse buckets (high 2 bits)

With 4 buckets, each covers 4 values. The "bucket index" of a number is just v >> 2 (the high 2 bits of a 4-bit number).

Cumulative count first reaches the target (8) at bucket 1. So:

Pass 2 — sub-buckets (low 2 bits, only for bucket 1)

Re-stream both files. Filter to values in bucket 1 (range 4–7). Increment sub[v & 0b11] for each.

Cumulative first reaches needRank = 2 at sub-bucket 1. The actual value is (medianBucket << 2) | 1 = (1 << 2) | 1 = 5. ✓

Memory, I/O, and wall-clock time

Now that the shape of the algorithm is clear, let's price it out for the real 40 GB problem.

Why the I/O numbers matter more than the CPU numbers

At 40 GB, every second of wall-clock time is dictated by how many bytes you move. A modern NVMe SSD reads at 3–5 GB/s sequential; a SATA SSD at 500 MB/s; a network-attached blob store at maybe 200 MB/s. The bucket method's win isn't that it's smarter — it's that it does less I/O and the I/O it does is purely sequential, which is the fastest mode on every storage medium.

How to actually read the files fast

Three rules of thumb that turn this from "an algorithm" into "a program that finishes":

• ›Big buffered reads. Use 8–64 MB read buffers. Don't read int-by-int; read a slab, parse it in memory.
• ›One thread per file. 50 files, 50 reader threads. Each thread keeps a local 65k bucket array, then a final reduction step sums them. No contention, no locks.
• ›Memory-mapped I/O if your OS permits it. mmap lets the kernel page in file pages on demand and skip a userspace copy. For sequential scans of bounded-size files it's often the single biggest win.

The edge cases that get asked in interviews

The two-pass story is the headline. The rest of this section is the small print that separates a good answer from a great one.

Pointers worth knowing about

• ›Quickselect on disk. The classical alternative — pick a pivot, partition, recurse on the half containing rank K. Average-case great, worst-case awful (bad pivot choice can blow up). Bucket counting is deterministic and pivot-free; that's why it wins at scale.
• ›This is just radix selection. What you've learned is the disk-friendly form of radix selection (a cousin of radix sort). The "two passes of 16 bits" is two iterations of radix narrowing. Useful term to know.
• ›MapReduce-able. Pass 1 is a map (emit bucket-index per int) followed by a reduce (sum bucket counts). Pass 2 is the same with a filter. Drop this into Spark / Flink / a Hadoop job and you can scale it to petabytes.
• ›Generalizes to any percentile. The 50th percentile (median) was illustrative. Replace target = N/2 with target = N * p for the p-th percentile. Same two passes. Useful when you need P95, P99, etc. on huge logs.

When buckets don't work — and what replaces them

The bucket method has one hard prerequisite: the values must come from a bounded, discretizable range that you can carve into buckets ahead of time. When that breaks, you need a different tool. Three real-world cases:

The 60-second version

If someone stops you in the hallway and asks you to explain the whole article in a minute, here's the script.