skip to content

Sorting 500 GB with 4 GB of memory and 4 MB I/O buffers, how many external merge sort passes?

level: middleimportance: should knowfreq 48%

answer

  1. start by counting the runs
  2. memory divided by buffer size gives buffers
  3. one buffer must hold the output
  4. the merge is k-way, not binary
  5. run generation is itself a full pass

basics

~20 s

Two passes, about 2 TB of I/O. Run generation writes 125 memory-sized sorted runs; 4 GB of 4 MB buffers gives a fan-in of 1023 after reserving one for output, so all 125 merge in one pass.

solid answer

~50 s

Three numbers do the whole job. **Runs**: `ceil(500 GB / 4 GB)` = 125 sorted runs from phase one. **Fan-in**: memory divided by buffer size gives 1024 buffers, minus one reserved for output, so 1023 runs can be merged at once. **Merge passes**: `ceil(log_1023(125))` = 1, because 125 fits under the fan-in. Total = 1 run-generation pass + 1 merge pass = **2 passes**. Since a pass reads and writes every byte, that is about 2 TB of I/O for 500 GB of data. The general form is `passes = 1 + ceil(log_F(ceil(N/M)))` with fan-in `F = floor(M/b) - 1`. The two mistakes that show up here are forgetting that run generation is itself a pass, and taking `log2` of the run count instead of `log` base fan-in — the merge is k-way, not binary.

go deeper

for a junior

Know the two quantities the arithmetic starts from: the run count is input size divided by sort memory, and the merge needs one buffer per run being merged. Being able to state that run generation is itself a pass already puts you ahead.

for a middle

Derive the whole formula out loud: runs = ceil(N/M), fan-in = memory/buffer minus one for output, passes = 1 + ceil(log base fan-in of runs). Then convert passes into bytes moved, since a pass reads and writes everything.

for a senior

Expect the sensitivity question. Show that the pass count is an integer step function, identify where the boundaries sit (run count crossing the fan-in, then its square), and say which knob you would turn to cross one.

for a principal

Own the budget conversation. Translate a pass into money and elapsed time against the batch window, then argue whether more memory, more devices, narrower records, or a changed ordering requirement is the cheapest way to hit it.

## The three quantities External merge sort costs are counted in **passes**, where one pass reads every byte once and writes every byte once. Everything else is arithmetic on three inputs: the data size `N`, the sort memory `M`, and the I/O buffer size `b`. **Run count.** Phase one fills the sort buffer, sorts it in memory, and writes it out as a sorted run. So the number of runs is `R = ceil(N / M)`. With `N = 500 GB` and `M = 4 GB`, `R = 125`. **Fan-in.** The merge phase needs one input buffer per run it is merging concurrently, plus at least one output buffer to accumulate results before writing. With `M = 4 GB` and `b = 4 MB`, memory holds `1024` buffers, so the fan-in is `F = 1024 - 1 = 1023`. **Merge passes.** Each merge pass reduces the number of runs by a factor of `F`, since `F` runs collapse into one longer run. Starting from `R` runs you need `ceil(log_F(R))` merge passes. Here `log_1023(125) < 1`, so a single merge pass suffices — 125 runs is comfortably under a fan-in of 1023. **Total.** `passes = 1 + ceil(log_F(R))` = `1 + 1` = **2**. ## Turning passes into bytes and time | Quantity | Value | |---|---| | Input size `N` | 500 GB | | Sort memory `M` | 4 GB | | Runs `R = ceil(N/M)` | 125 | | Buffers `M/b` | 1024 | | Fan-in `F = M/b - 1` | 1023 | | Merge passes `ceil(log_F R)` | 1 | | Total passes | 2 | | Bytes moved (2 × 2N) | ~2 TB | A pass over 500 GB moves about 1 TB (500 GB read plus 500 GB written), so two passes move about 2 TB. Divide by the device's sustained sequential bandwidth for a first-order runtime estimate. That estimate is usable precisely because the I/O is sequential and the comparison work can be overlapped with it. ## The two arithmetic errors people actually make **Forgetting that run generation is a pass.** Candidates often answer "one pass" here, counting only the merge. But phase one reads all 500 GB and writes all 500 GB back as runs; that is a full pass by the same definition, and it is half the total I/O in this configuration. **Using `log2` instead of `log F`.** Merging is `k`-way, not binary. Someone who reaches for `log2(125) ≈ 7` gets eight passes and concludes the job is hopeless, when the correct answer is two. The whole point of a large fan-in is that the logarithm has a base in the hundreds or thousands, which collapses the merge to one or two rounds for almost any realistic data size. A third, subtler slip is forgetting the output buffer, giving `F = 1024`. It changes nothing here, but it is the kind of off-by-one that matters when the run count sits right at the fan-in boundary — with 1024 runs and a true fan-in of 1023, you need two merge passes, not one. ## What more memory actually buys This is the question a skeptical reviewer asks next: if we double the machine's memory to 8 GB, how much faster is the sort? Doubling `M` does two things at once. Runs halve — `R` goes from 125 to 63 — **and** fan-in doubles, from 1023 to 2047. Both moves shrink `ceil(log_F R)`, which is why extra memory is so effective in the region where the merge still takes several passes. But the pass count is an **integer**, and it is already floored at 2 here: you cannot merge without reading the runs, so 2 passes is the minimum for any data that does not fit in memory. Doubling memory in this configuration buys faster in-memory sorting in phase one and fewer, larger sequential writes — not a smaller pass count. The same arithmetic run on a smaller box shows where memory does pay. With `M = 512 MB` and the same 4 MB buffers: `R = ceil(500/0.5) = 1000` runs, `F = 128 - 1 = 127`, and `ceil(log_127(1000)) = 2` merge passes because 1000 exceeds 127 but is far below `127² = 16129`. Total: **3 passes**, about 3 TB of I/O — fifty percent more work than the 4 GB machine. Going from 512 MB to 4 GB removes a whole pass; going from 4 GB to 8 GB removes none. That step-function behaviour is the practical lesson. Effort spent on memory, buffer sizing, or record width pays only when it moves the job across an integer pass boundary. Knowing where the boundaries sit — the run count crossing `F`, then `F²` — is what lets you say whether a proposed change is worth anything before you make it.

  • What does doubling the machine's memory to 8 GB buy in this configuration?
    Nothing in pass count. Doubling memory halves the runs (125 to 63) and doubles the fan-in (1023 to 2047), but the job is already at the two-pass floor — no external sort can do better, since the runs must at least be written and read back. You gain faster in-memory sorting and fewer, larger sequential writes. Memory pays when the merge currently needs two or more rounds.
  • Redo the arithmetic with only 512 MB of memory — how many passes?
    Three. Runs = ceil(500 GB / 0.5 GB) = 1000. Buffers = 512 MB / 4 MB = 128, so fan-in = 127. Since 1000 exceeds 127 but is far below 127² = 16129, the merge needs two passes, plus the run-generation pass. That is about 3 TB of I/O versus 2 TB on the 4 GB machine — fifty percent more work.
  • Is two passes the theoretical minimum here?
    Yes for data that does not fit in memory. Phase one must read the input and write sorted runs somewhere, and the merge must read those runs and write the result — that is two reads and two writes of every byte. Only if the whole input fit in memory could you finish in a single read-sort-write.

saying these in an interview costs you the question

  • Forgets that run generation is itself a full pass
  • Takes log base 2 of the run count instead of log base fan-in
  • Uses every buffer for input and reserves none for output
  • Counts a pass as reading the data only, not reading and writing
  • Assumes more memory always reduces the pass count

context

resolving links…