---
title: External Sorting
module: Sorting & Order Statistics
moduleNumber: 3
lessonNumber: 4
order: 304
summary: |
  When the data dwarfs main memory, the cost that matters is no longer
  comparisons but block transfers to and from disk. External merge sort sorts
  memory-sized runs, then folds them together with a heap-driven $k$-way merge in
  $\Theta(\log_k(N/M))$ passes. Larger fan-out cuts passes; replacement selection
  builds longer runs to cut them further.
topics: [External Sorting, Comparison Sorting]
sources:
  - book: CLRS
    ref: "Problem 6-3, Ch. 11 — external storage and merging"
  - book: Skiena
    ref: "§4.6 — External Sorting"
  - book: Erickson
    ref: "Ch. — Sorting"
practice:
  - title: 'Merge k Sorted Lists'
    slug: merge-k-sorted-lists
    difficulty: Hard
  - title: 'Find K Pairs with Smallest Sums'
    slug: find-k-pairs-with-smallest-sums
    difficulty: Medium
  - title: 'Kth Smallest Element in a Sorted Matrix'
    slug: kth-smallest-element-in-a-sorted-matrix
    difficulty: Medium
---

Every sort we have met so far, [heapsort](/algorithms/sorting/heaps-and-heapsort),
[mergesort](/algorithms/divide-and-conquer/mergesort), the
[linear-time sorts](/algorithms/sorting/linear-time-sorting), shares a hidden
assumption: the whole array fits in fast memory, and any element is as cheap to
touch as any other. When the data is larger than RAM, a database table of a
hundred gigabytes on a machine with eight of them, that assumption collapses. The
array lives on disk, and the cost of the sort is no longer how many times we
_compare_ but how many times we _move a block between disk and memory_. This
lesson is about sorting under that constraint: **external**, or **out-of-core**,
sorting.

## Why the in-memory cost model lies

A disk does not behave like slower random-access memory. Reaching an arbitrary
byte costs a **seek** (moving the head, or, on flash, an erase-block penalty)
that is four to five orders of magnitude slower than a memory reference. To amortize
that latency, storage is read and written in fixed-size **blocks** of $B$ records
at a time; once the head is positioned, the marginal cost of the rest of the block
is small. The realistic accounting therefore counts **block transfers**, not
comparisons.

> **Definition (External-memory model).** Memory holds $M$ records; disk is
> unbounded and is read and written in blocks of $B$ records. An algorithm's cost
> is the number of block transfers (**I/Os**) between disk and memory. CPU work on
> data already in memory is treated as free.

This change of cost model reorders the algorithm rankings. Consider running ordinary
[quicksort](/algorithms/divide-and-conquer/quicksort) on data that does not fit
in memory, with the array paged in and out by the operating system. Its partition
step sweeps the array with two pointers that jump unpredictably, and its
recursion touches scattered regions. Each stray access can force a fresh block
transfer, so an algorithm that is $\Theta(N\log N)$ in _comparisons_ can degrade
toward one block transfer per comparison, thrashing the disk. The $\log N$ that
looked harmless is now multiplied by a constant measured in milliseconds.

> **Remark (The real enemy is the seek).** In-memory we optimize the comparison
> count because comparisons dominate. On disk a sequential scan of $N$ records
> costs only $\lceil N/B \rceil$ transfers, cheap, while $N$ scattered accesses
> cost up to $N$ transfers, ruinous. A good external algorithm is one that touches
> the disk in long sequential streams and almost never seeks.

The design goal flips accordingly. We want an algorithm whose disk traffic is a
handful of **linear sequential passes** over the data, and we will measure it by
counting those passes.

## External merge sort

The right strategy descends directly from [mergesort](/algorithms/divide-and-conquer/mergesort),
whose merge step is already a sequential streaming operation: it reads two sorted
inputs front to back and writes one sorted output front to back, never seeking.
That is the access pattern disk handles cheaply. External merge sort is
mergesort reorganized into two phases that respect the block model.

> **Definition (Run).** A **run** is a maximal sorted contiguous stretch of
> records on disk. The sort's job is to produce one run of length $N$ from an
> unsorted file.

**Phase 1 — run formation.** Read the file one memory-load at a time. Each load of
up to $M$ records is sorted in memory by any internal sort, [heapsort](/algorithms/sorting/heaps-and-heapsort)
or quicksort, then written back out as a sorted run. A file of $N$ records yields
about $\lceil N/M \rceil$ initial runs, each of length $M$ (the last possibly
shorter). This phase reads the whole file once and writes it once: $2\lceil N/B \rceil$
transfers, two sequential passes.

$$
% caption: Run formation (phase 1). The unsorted file streams past in memory-sized loads of
%          $M$ records; each load is sorted internally and flushed back as one sorted run.
%          A file of $N$ records becomes $\lceil N/M\rceil$ runs.
\begin{tikzpicture}[
  cell/.style={draw, minimum width=6mm, minimum height=6mm, font=\scriptsize, inner sep=0pt},
  lbl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  % unsorted file, three loads delimited by the memory window
  \node[lbl, anchor=east] at (-0.3,3.0) {input};
  \foreach \v/\i in {52/0,31/1,40/2}   \node[cell, fill=black!7] at (\i*0.62,3.0) {\v};
  \foreach \v/\i in {19/3,77/4,28/5}   \node[cell, fill=black!7] at (\i*0.62,3.0) {\v};
  \foreach \v/\i in {63/6,11/7,45/8}   \node[cell, fill=black!7] at (\i*0.62,3.0) {\v};
  % the memory window brackets one load
  \draw[draw=acc, thick] (-0.32,2.62) rectangle (1.55,3.38);
  \node[lbl, anchor=south, text=acc] at (0.61,3.42) {load of $M$};
  % internal sort
  \node[lbl, anchor=east] at (-0.3,1.5) {sort in memory};
  \node[cell, fill=acc!18, draw=acc] at (0,1.5) {31};
  \node[cell, fill=acc!18, draw=acc] at (0.62,1.5) {40};
  \node[cell, fill=acc!18, draw=acc] at (1.24,1.5) {52};
  \draw[->, >=Stealth, acc] (0.61,2.55) -- (0.61,1.85);
  % flushed sorted runs
  \node[lbl, anchor=east] at (-0.3,0.0) {sorted runs};
  \foreach \v/\i in {31/0,40/1,52/2} \node[cell, fill=acc!18, draw=acc] at (\i*0.62,0.0) {\v};
  \foreach \v/\i in {19/4,28/5,77/6} \node[cell, fill=acc!18, draw=acc] at (\i*0.62,0.0) {\v};
  \foreach \v/\i in {11/8,45/9,63/10} \node[cell, fill=acc!18, draw=acc] at (\i*0.62,0.0) {\v};
  \draw[->, >=Stealth, acc] (0.61,1.15) -- (0.61,0.4);
  \node[lbl, anchor=south] at (0.61,-0.62) {run 1};
  \node[lbl, anchor=south] at (2.78,-0.62) {run 2};
  \node[lbl, anchor=south] at (5.27,-0.62) {run 3};
  \node[lbl, anchor=west] at (6.4,1.5) {repeat per load};
\end{tikzpicture}
$$

**Phase 2 — merging.** We now have many sorted runs and must combine them into
one. Merging two runs at a time, as plain mergesort does, would take $\log_2(N/M)$
passes over the data. We do far better by merging $k$ runs **at once** in a single
pass, a **$k$-way merge**, repeating until one run remains.

$$
% caption: External merge sort. Phase 1 sorts memory-sized loads into
%          $\lceil N/M\rceil$ runs; phase 2 folds them $k$ at a time, each pass a
%          full sequential sweep, until a single sorted run of length $N$ remains.
\begin{tikzpicture}[
  run/.style={draw, minimum width=15mm, minimum height=6mm, font=\scriptsize, inner sep=1pt},
  lbl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  % unsorted file
  \node[run, fill=black!8] (u) at (0,2.4) {unsorted};
  \node[lbl, anchor=south] at (0,2.85) {input ($N$)};
  % phase 1 runs
  \foreach \i/\y in {1/1.2,2/0.4,3/-0.4,4/-1.2}
    \node[run, fill=acc!12] (r\i) at (2.6,\y) {run \i};
  \draw[->, >=Stealth] (u.south) to[out=-90,in=180] (r1.west);
  \draw[->, >=Stealth] (u.south) to[out=-90,in=180] (r2.west);
  \draw[->, >=Stealth] (u.south) to[out=-90,in=180] (r3.west);
  \draw[->, >=Stealth] (u.south) to[out=-90,in=180] (r4.west);
  \node[lbl, anchor=south] at (2.6,1.65) {sorted runs};
  % intermediate after one k=2 pass
  \node[run, fill=acc!20] (m1) at (5.6,0.8) {merged A};
  \node[run, fill=acc!20] (m2) at (5.6,-0.8) {merged B};
  \draw[->, >=Stealth] (r1.east) to[out=0,in=180] (m1.west);
  \draw[->, >=Stealth] (r2.east) to[out=0,in=180] (m1.west);
  \draw[->, >=Stealth] (r3.east) to[out=0,in=180] (m2.west);
  \draw[->, >=Stealth] (r4.east) to[out=0,in=180] (m2.west);
  % final run
  \node[run, fill=grn!20, draw=grn] (f) at (8.4,0) {sorted ($N$)};
  \draw[->, >=Stealth] (m1.east) to[out=0,in=180] (f.west);
  \draw[->, >=Stealth] (m2.east) to[out=0,in=180] (f.west);
  \node[lbl, anchor=north] at (4.1,-1.7) {each arrow layer is one sequential pass};
\end{tikzpicture}
$$

### The k-way merge

The core step is selecting, repeatedly, the smallest record among
$k$ sorted runs. Naively scanning all $k$ run fronts on every step costs $\Theta(k)$
per record; across $N$ records that is $\Theta(Nk)$ comparisons, throwing away
the savings of a large fan-out. The fix is a structure we already own: a
**min-heap**, the [priority queue](/algorithms/sorting/heaps-and-heapsort) from
the heap lesson, holding one candidate, the current front record, from each run.
Its root is the global minimum, extracted in $O(\log k)$, and when a run supplies
its next record we sift that in for another $O(\log k)$.

```algorithm
caption: $\textsc{k-Way-Merge}(R_1, \dots, R_k)$ — merge $k$ sorted runs into one
number: 1
let $H$ be an empty min-heap keyed on record value
for $i \gets 1$ to $k$ do
  if run $R_i$ is nonempty then
    $x \gets$ read first record of $R_i$
    $\textsc{Insert}(H, (x, i))$ // tag each candidate with its run
while $H$ is nonempty do
  $(x, i) \gets \textsc{Extract-Min}(H)$ // smallest across all run fronts
  output $x$ // append to the merged run
  if run $R_i$ has a next record then
    $y \gets$ read next record of $R_i$
    $\textsc{Insert}(H, (y, i))$ // refill from the run we drained
```

The heap never holds more than $k$ records, one per run, so it occupies $\Theta(k)$
memory regardless of how long the runs are. Each of the $N$ output records costs
one $\textsc{Extract-Min}$ and at most one $\textsc{Insert}$, so a $k$-way merge
runs in $\Theta(N\log k)$ comparisons, improving the per-record cost from
$\Theta(k)$ to $\Theta(\log k)$ over the naive scan.

$$
% caption: The reload step. The root $14$ (the run-3 head) is extracted and emitted; run~3
%          advances, supplying $19$, which is sifted down into the now-empty root and settles,
%          restoring the heap in $O(\log k)$. The green root is the correct minimum being taken.
\begin{tikzpicture}[
  n/.style={circle, draw, minimum size=8mm, font=\small, inner sep=0pt},
  lbl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  % before
  \node[lbl] at (1.0,3.0) {before};
  \node[n, fill=grn!22, draw=grn] (a1) at (1.0,2.3) {14};
  \node[n, fill=acc!12] (a2) at (0.2,1.2) {22};
  \node[n, fill=acc!12] (a3) at (1.8,1.2) {18};
  \node[n, fill=acc!12] (a4) at (0.2,0.1) {31};
  \draw (a1)--(a2); \draw (a1)--(a3); \draw (a2)--(a4);
  % extract + emit
  \node[lbl, text=grn] at (3.6,2.3) {emit 14};
  \draw[->, >=Stealth, grn, thick] (1.95,2.3) -- (2.95,2.3);
  \node[lbl] at (3.6,1.5) {run 3 gives 19};
  % after
  \node[lbl] at (6.2,3.0) {after};
  \node[n, fill=grn!22, draw=grn] (b1) at (6.2,2.3) {18};
  \node[n, fill=acc!12] (b2) at (5.4,1.2) {22};
  \node[n, fill=acc!12] (b3) at (7.0,1.2) {19};
  \node[n, fill=acc!12] (b4) at (5.4,0.1) {31};
  \draw (b1)--(b2); \draw (b1)--(b3); \draw (b2)--(b4);
  \draw[->, >=Stealth, acc] (4.4,1.5) -- (5.3,1.5);
  \node[lbl, anchor=west, text=grn] at (7.05,2.3) {new min};
\end{tikzpicture}
$$

$$
% caption: A $4$-way merge. The min-heap holds the head record of each of the four
%          input runs; its root ($14$) is the next output. After emitting it, the run it
%          came from advances and the new head is sifted in.
\begin{tikzpicture}[
  buf/.style={draw, minimum width=7mm, minimum height=6mm, font=\scriptsize, inner sep=0pt},
  n/.style={circle, draw, minimum size=8mm, font=\small, inner sep=0pt},
  lbl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  % four input buffers on the left, fronts highlighted
  \foreach \r/\y/\a/\b/\c in {1/3.0/14/27/40, 2/2.0/22/35/51, 3/1.0/19/30/46, 4/0.0/31/38/55} {
    \node[lbl, anchor=east] at (-0.2,\y) {run \r};
    \node[buf, fill=acc!15, draw=acc, thick] (f\r) at (0.4,\y) {\a};
    \node[buf] at (1.1,\y) {\b};
    \node[buf] at (1.8,\y) {\c};
  }
  \node[lbl, anchor=south] at (1.1,3.6) {input runs (heads shaded)};
  % min-heap in the middle
  \node[n, fill=grn!22, draw=grn] (h1) at (4.3,3.0) {14};
  \node[n] (h2) at (3.6,1.9) {19};
  \node[n] (h3) at (5.0,1.9) {22};
  \node[n] (h4) at (3.6,0.8) {31};
  \draw (h1)--(h2); \draw (h1)--(h3); \draw (h2)--(h4);
  \node[lbl, anchor=south] at (4.3,3.7) {min-heap of heads};
  \node[lbl, text=grn, anchor=east] at (2.55,3.35) {top = next out};
  % each head drops to a clear channel at $y=-0.7$, runs right, then rises into
  % the heap from below, so no arrow crosses a buffer cell
  \draw[->, >=Stealth, acc!70] (f1.south) to[out=-90,in=180] (2.7,-0.7) to[out=0,in=-110] (h1.south west);
  \draw[->, >=Stealth, acc!40] (f2.south) to[out=-90,in=180] (2.9,-0.7) to[out=0,in=-120] (h3.south);
  \draw[->, >=Stealth, acc!40] (f3.south) to[out=-90,in=180] (2.5,-0.7) to[out=0,in=-90] (h2.south);
  \draw[->, >=Stealth, acc!40] (f4.south) to[out=-90,in=180] (2.3,-0.7) to[out=0,in=-90] (h4.south);
  % output stream
  \node[buf, fill=acc!22, draw=acc, thick] (o) at (7.6,1.4) {14};
  \node[lbl, anchor=south, text=acc] at (7.6,1.95) {output run};
  \draw[->, >=Stealth, grn, thick] (h1.east) to[out=0,in=110] (o.north);
  \node[lbl, anchor=west] at (5.9,3.4) {extract min,};
  \node[lbl, anchor=west] at (5.9,3.05) {then reload};
\end{tikzpicture}
$$

> **Note (Merge sort connection).** A $2$-way merge is the ordinary
> [mergesort](/algorithms/divide-and-conquer/mergesort) merge with $k=2$; there the
> "heap" degenerates to a single comparison between two fronts. External merge sort
> is simply mergesort with two changes: the base-case runs are sorted in bulk to
> fill memory, and the merge fans in $k$ runs at once instead of two, so the whole
> file is swept far fewer times.

::impl{algo="k_way_merge,external_merge_sort#external_merge_sort+form_runs+merge_pass+streaming_external_sort"}

## How many passes?

This is the figure of merit. Phase 1 produces $\lceil N/M \rceil$ runs. Each
merging pass reads every run once and writes the merged output once, a full
sequential sweep of the data, and replaces $k$ runs with one, dividing the run
count by $k$. We are done when the count reaches $1$.

> **Theorem (Pass count).** External merge sort with fan-out $k$ performs
> $$
> 1 + \Bigl\lceil \log_k \tfrac{N}{M} \Bigr\rceil
> $$
> sequential passes over the data: one run-formation pass plus
> $\lceil \log_k(N/M)\rceil$ merge passes.

> **Proof.** After phase 1 there are $r_0 = \lceil N/M\rceil$ runs. A $k$-way merge
> pass maps $r$ runs to $\lceil r/k\rceil$ runs, so after $p$ merge passes the run
> count is at most $\lceil r_0/k^p\rceil$. This reaches $1$ once $k^p \ge r_0$, that
> is at $p = \lceil \log_k r_0\rceil = \lceil \log_k(N/M)\rceil$. Adding the single
> run-formation pass gives the stated total. $\qed$

$$
% caption: Pass cascade with fan-out $k=4$ on $r_0=64$ initial runs. Each merge pass divides
%          the run count by $k$, so $64$ to $16$ to $4$ to $1$ takes three merge passes,
%          matching $\lceil\log_4 64\rceil=3$, plus the one run-formation pass.
\begin{tikzpicture}[
  box/.style={draw, minimum width=20mm, minimum height=7mm, font=\scriptsize, inner sep=1pt, fill=acc!14, draw=acc},
  grnbox/.style={draw, minimum width=20mm, minimum height=7mm, font=\scriptsize, inner sep=1pt, fill=grn!20, draw=grn},
  lbl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  \node[box] (a) at (0,3.2) {64 runs};
  \node[box] (b) at (0,2.0) {16 runs};
  \node[box] (c) at (0,0.8) {4 runs};
  \node[grnbox] (d) at (0,-0.4) {1 run (sorted)};
  \draw[->, >=Stealth, acc] (a.south) -- node[right, lbl] {merge pass 1 (divide by 4)} (b.north);
  \draw[->, >=Stealth, acc] (b.south) -- node[right, lbl] {merge pass 2 (divide by 4)} (c.north);
  \draw[->, >=Stealth, grn] (c.south) -- node[right, lbl] {merge pass 3 (divide by 4)} (d.north);
  \node[lbl, anchor=east] at (-1.3,3.2) {phase 1 output};
  \node[lbl, anchor=east, text=grn] at (-1.3,-0.4) {done};
\end{tikzpicture}
$$

Each pass moves the entire file, $\lceil N/B\rceil$ reads and $\lceil N/B\rceil$
writes, so the total I/O cost is

$$
\Theta\!\parens{ \frac{N}{B}\parens{1 + \log_k \frac{N}{M}} }
\;=\; \Theta\!\parens{ \frac{N}{B}\,\log_k \frac{N}{M} }
\text{ block transfers.}
$$

The base of the logarithm is what matters. Doubling the fan-out from $k=2$ to
$k=4$ halves the number of merge passes, because $\log_4 x = \tfrac12\log_2 x$. On
a terabyte file with gigabytes of memory the difference between a binary merge and
a wide one is the difference between dozens of passes and two or three.

$$
% caption: Merge passes versus fan-out for a fixed $N/M$. Passes fall as
%          $\lceil\log_k(N/M)\rceil$, so a wider merge flattens the file in far fewer
%          sequential sweeps; the gain shrinks as $k$ grows.
\begin{tikzpicture}
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  % axes
  \draw[->, >=Stealth] (0,0) -- (6.6,0) node[right, font=\scriptsize] {fan-out $k$};
  \draw[->, >=Stealth] (0,0) -- (0,4.2) node[above, font=\scriptsize] {merge passes};
  \foreach \k/\x in {2/0.7,4/1.7,8/2.7,16/3.7,64/4.7,256/5.7}
    \node[font=\scriptsize, anchor=north] at (\x,0) {\k};
  \foreach \p in {2,4,6,8} \node[font=\scriptsize, anchor=east] at (-0.1,\p*0.45) {\p};
  % passes for N/M = 2^16: log_k(2^16) = 16/log2(k)
  % k=2 ->16(cap 8), 4->8, 8->5.33, 16->4, 64->2.67, 256->2
  \draw[acc, very thick]
    (0.7,3.6) -- (1.7,3.6) -- (2.7,2.4) -- (3.7,1.8) -- (4.7,1.2) -- (5.7,0.9);
  \foreach \x/\y in {0.7/3.6,1.7/3.6,2.7/2.4,3.7/1.8,4.7/1.2,5.7/0.9}
    \fill[acc] (\x,\y) circle (2pt);
  \node[font=\scriptsize, text=acc, anchor=west] at (1.9,3.7) {fewer passes as $k$ grows};
\end{tikzpicture}
$$

::impl{algo="external_merge_sort#pass_count"}

### Why not make k enormous?

If a bigger $k$ always helps, why not merge all $\lceil N/M\rceil$ runs in one
pass? Because fan-out is bounded by **memory**. During a merge the $M$ records of
memory are divided into one **input buffer** per run plus an output buffer; each
buffer must hold at least one block of $B$ records to keep the disk traffic
sequential. With $k$ input buffers and an output buffer we need roughly
$(k+1)B \le M$, so

$$
k \;\le\; \frac{M}{B} - 1.
$$

Push $k$ past this and the buffers shrink below a block, the merge starts seeking
within each run, and the per-record I/O cost explodes, exactly the thrashing we
set out to avoid. So $k$ is chosen near $M/B$: large enough that $\log_k(N/M)$ is
typically $1$ or $2$, small enough that every buffer is at least one block. There
is also a CPU-side tension, the heap costs $\Theta(N\log k)$ comparisons, but on
disk-bound sorts the I/O term dominates and the comparison cost is secondary.

> **Intuition (The buffer budget).** Memory is split among the runs you are
> merging. More runs means more passes saved but thinner buffers; thinner buffers
> than a block means seeking, which is catastrophic. The sweet spot fills memory
> with one block-sized buffer per run, fanning in $\approx M/B$ runs at a time.

::impl{algo="external_merge_sort#max_fan_out"}

## Replacement selection: longer initial runs

The pass count is $\lceil \log_k(N/M)\rceil$, driven by the _number_ of initial
runs, $N/M$. Anything that makes the initial runs **longer** shrinks $N/M$ and can
remove a whole pass. Phase 1 as described caps each run at $M$, the memory size.
**Replacement selection** beats that bound, producing runs of average length
$2M$.[^skiena-ext]

The idea treats memory as a min-heap of $M$ records that continuously consumes
input and emits output, rather than sorting in fixed batches. Fill the heap with
$M$ records. Repeatedly extract the minimum and append it to the current run; then
read the next input record and decide where it goes. If it is $\ge$ the record
just emitted, it can still belong to the current run, so insert it into the heap.
If it is _smaller_, it cannot, so set it aside (mark it "frozen") to seed the
**next** run. The current run grows as long as incoming records keep up with the
output; only when the heap is entirely frozen records do we close the run and
start fresh.

```algorithm
caption: $\textsc{Replacement-Selection}$ — form long runs with an $M$-record heap
number: 2
fill min-heap $H$ with the first $M$ input records
$last \gets -\infty$ // last value written to the current run
while $H$ is nonempty do
  $x \gets \textsc{Extract-Min}(H)$ // smallest unfrozen record
  output $x$ to the current run
  $last \gets x$
  if more input remains then
    $y \gets$ read next input record
    if $y \ge last$ then
      $\textsc{Insert}(H, y)$ // still fits this run
    else
      freeze $y$ for the next run // mark, keep in memory
  if $H$ has only frozen records then
    close current run; unfreeze all; start a new run
```

Why $2M$ on average? Picture the input as a stream and the heap as a window of
$M$ records sliding along it. A new record extends the current run whenever it is
no smaller than the last output, which for random data happens about half the time
at any moment, but the records that _do_ extend the run push the window forward
and let still more records qualify. The classic "snowplow" argument makes it
precise: a plow clears snow on a circular road while snow keeps falling uniformly;
in steady state the plow always has about twice its own length of snow ahead of it.
The same balance yields runs of expected length $2M$, and on already-sorted or
nearly-sorted input a _single_ run covering the entire file.[^clrs-ext]

$$
% caption: Replacement selection. Records arriving $\ge$ the last output (green) extend the
%          current run through the heap; smaller arrivals (blue outline) are frozen in memory to
%          seed the next run. Average run length $\approx 2M$, double a fixed-batch sort.
\begin{tikzpicture}[
  rec/.style={draw, minimum width=6.5mm, minimum height=6mm, font=\scriptsize, inner sep=0pt},
  lbl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  % incoming stream: green = extends run, blue outline = frozen
  \node[lbl, anchor=east] at (-0.2,2.8) {input};
  \node[rec, fill=grn!18, draw=grn] at (0,2.8) {17};
  \node[rec, fill=grn!18, draw=grn] at (0.85,2.8) {25};
  \node[rec, fill=white, draw=acc, thick] at (1.7,2.8) {9};
  \node[rec, fill=grn!18, draw=grn] at (2.55,2.8) {30};
  \node[rec, fill=white, draw=acc, thick] at (3.4,2.8) {12};
  \node[rec, fill=grn!18, draw=grn] at (4.25,2.8) {41};
  \node[lbl, anchor=west] at (5.0,2.8) {arriving records};
  % heap box
  \draw[draw=acc, thick] (0.7,1.0) rectangle (4.1,2.0);
  \node[lbl, anchor=south, text=acc] at (2.4,2.05) {min-heap (size $M$)};
  \node[rec, fill=acc!12] at (1.2,1.5) {17};
  \node[rec, fill=acc!12] at (1.9,1.5) {25};
  \node[rec, fill=acc!12] at (2.6,1.5) {30};
  \node[rec, fill=acc!12] at (3.3,1.5) {41};
  % frozen pile
  \node[lbl, anchor=west, text=acc] at (4.4,1.5) {frozen 9, 12 seed next run};
  % output run, well below the heap box and its label
  \node[lbl, anchor=east] at (-0.2,-0.4) {current run};
  \foreach \v/\i in {5/0,8/1,11/2,14/3} \node[rec, fill=grn!18, draw=grn] at (\i*0.85,-0.4) {\v};
  \node[lbl, anchor=west] at (3.2,-0.4) {sorted output, about twice memory long};
  \draw[->, >=Stealth, grn, thick] (2.4,0.95) to[out=-90,in=90] (1.7,-0.04);
\end{tikzpicture}
$$

$$
% caption: The snowplow argument. On a circular road snow falls uniformly while one plow
%          clears it; in steady state the plow always faces about twice its own length of
%          snow. The heap is the plow, the cleared length is one run, hence runs $\approx 2M$.
\begin{tikzpicture}[
  lbl/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  % circular road
  \draw[black, line width=5pt] (0,0) circle (1.5);
  % snow ahead of the plow: the acc arc spanning the upcoming, uncleared stretch
  \draw[acc, line width=5pt] (1.5,0) arc (0:230:1.5);
  % the plow
  \fill[acc] (1.5,0) circle (3pt);
  \node[lbl, anchor=west, text=acc] at (1.75,0) {plow (heap)};
  \node[lbl, anchor=east, text=acc] at (-1.15,1.25) {snow ahead};
  \node[lbl, anchor=east, text=black] at (-0.2,-1.4) {cleared};
  % the relation
  \node[lbl, anchor=west] at (3.4,0.6) {snow ahead is about twice plow length};
  \node[lbl, anchor=west] at (3.4,0.0) {cleared per cycle is about double};
  \node[lbl, anchor=west] at (3.4,-0.6) {so each run averages two memory loads};
\end{tikzpicture}
$$

Roughly halving the run count this way often saves exactly one merge pass, a
sizable fraction of the disk traffic. Modern external sorts combine wide
fan-out merging with replacement-selection run formation, and on real workloads
the whole sort finishes in a small constant number of passes over the data.

::impl{algo="replacement_selection"}

## The disk-block connection: B-trees

The same accounting that shapes external sorting shapes external _search_. When a
sorted index is too big for memory, a balanced binary search tree is a poor fit:
its height is $\log_2 N$, and following each child pointer can cost a fresh block
transfer, so a lookup costs $\Theta(\log_2 N)$ seeks. A [B-tree](/algorithms/data-structures/b-trees)
fixes this with the same fan-out idea external merge sort uses. Pack
each node with as many keys as fill one block, $\Theta(B)$ of them, so each node
has $\Theta(B)$ children instead of $2$. The tree's height collapses from
$\log_2 N$ to

$$
\Theta\!\parens{\log_B N},
$$

and a search touches only $\Theta(\log_B N)$ blocks — the same $\log_k$ savings,
with the block size $B$ playing the fan-out $k$. A wide node is to search what a
wide merge is to sorting.

> **Takeaway.** Both structures solve the same problem, keeping a large
> ordered collection on disk while touching as few blocks as possible, and both
> solve it the same way: make the branching factor as wide as a block allows. External merge
> sort fans in $\approx M/B$ runs per pass; a B-tree fans out $\approx B$ children
> per node. Each turns a base-$2$ logarithm into a base-$B$ one.

## Past the two-parameter model

External merge sort is tuned to two parameters, memory size $M$ and block size
$B$, that it must be told. Two developments push past that dependence, and one
scales the idea across an entire datacenter.

**The optimal I/O bound.** The pass-count analysis gives
$\Theta(\tfrac{N}{B}\log_{M/B}\tfrac{N}{B})$ block transfers with fan-out
$k \approx M/B$. Aggarwal and Vitter (1988) proved this is **optimal**: no
external sorting algorithm, comparison-based, can do asymptotically fewer I/Os.
So external merge sort is to the block model what mergesort is to the comparison
model — provably the best possible up to constants.

**Cache-oblivious sorting.** External merge sort needs $M$ and $B$ hard-coded to
size its buffers. A **cache-oblivious** algorithm hits the same optimal I/O bound
_without knowing $M$ or $B$_, so a single binary runs optimally across every level
of the memory hierarchy at once — registers, L1, L2, RAM, disk — each with its own
unknown block size. **Funnelsort** (Frigo, Leiserson, Prokop, and Ramachandran,
1999) achieves this by merging through recursively-built "$k$-funnels" whose
sizes form a geometric ladder; the recursion automatically arranges that whatever
the true block size turns out to be, the data movement near that scale is
sequential. It is the same $k$-way-merge idea, made self-tuning.

**Sorting a datacenter: TeraSort.** When the data outgrows one machine's disks, the
merge fans out across a cluster. The **MapReduce** sort (and the **TeraSort**
benchmark built on it) is external merge sort's distributed cousin: a sampling pass
picks $k-1$ **splitter** keys that partition the key range into $k$ roughly equal
bands, each node range-partitions its shard by shipping records to the node owning
their band (the "shuffle"), and each node sorts its band locally. Concatenating the
bands in order yields a globally sorted file — a distributed bucket sort whose
splitters play the role of bucket boundaries, and whose per-node local sort is
itself an external merge sort. Sorting a petabyte this way is a standard
industry benchmark.

**Solid-state storage.** The model here charges a flat cost per block transfer, which
suited spinning disks where the seek dominated. Flash storage changes the constants:
random reads are nearly as cheap as sequential, but writes are expensive, must
happen in large erase blocks, and wear the device out. Modern external sorts on SSDs
therefore optimize for **write minimization** and large sequential writes rather
than seek avoidance — the accounting shifts, but the core strategy, few sequential
passes with wide fan-out, carries over.[^skiena-ext]

$$
% caption: Fan-out shrinks the depth. A binary structure over $N$ items is $\log_2 N$ deep;
%          a block-wide one is $\log_B N$ deep. The same idea drives $k$-way merge (fewer
%          passes) and the B-tree (fewer seeks per search).
\begin{tikzpicture}[font=\footnotesize, >=Stealth, x=1cm, y=1cm,
  n/.style={draw, circle, minimum size=4mm, inner sep=0},
  wide/.style={draw, minimum width=30mm, minimum height=5mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  % binary tree: tall
  \node[n, fill=acc!12] (r) at (0,2.6) {};
  \node[n, fill=acc!12] (a) at (-0.8,1.7) {}; \node[n, fill=acc!12] (b) at (0.8,1.7) {};
  \node[n, fill=acc!12] (c) at (-1.2,0.8) {}; \node[n, fill=acc!12] (d) at (-0.4,0.8) {};
  \node[n, fill=acc!12] (e) at (0.4,0.8) {}; \node[n, fill=acc!12] (f) at (1.2,0.8) {};
  \draw (r)--(a); \draw (r)--(b); \draw (a)--(c); \draw (a)--(d); \draw (b)--(e); \draw (b)--(f);
  \node[font=\footnotesize, anchor=north] at (0,0.4) {\texttt{binary: depth log2 N}};
  % B-tree: shallow, wide nodes
  \node[wide, fill=acc!14, draw=acc] (br) at (6,2.5) {};
  \node[wide, minimum width=13mm, fill=acc!14, draw=acc] (bl1) at (4.7,1.4) {};
  \node[wide, minimum width=13mm, fill=acc!14, draw=acc] (bl2) at (7.3,1.4) {};
  \draw[acc] (br.south) -- (bl1.north); \draw[acc] (br.south) -- (bl2.north);
  \node[font=\footnotesize, anchor=north] at (6,0.9) {\texttt{block-wide: depth logB N}};
\end{tikzpicture}
$$

## Takeaways

- On data larger than memory the cost model changes: we count **block transfers**
  (I/Os), not comparisons, and seeks dwarf everything, so good algorithms move the
  disk in long **sequential passes**.
- **External merge sort** has two phases: form $\lceil N/M\rceil$ sorted **runs**
  of memory size, then repeatedly **$k$-way merge** them until one run remains.
- The **$k$-way merge** uses a **min-heap** of the $k$ run fronts to emit the next
  smallest record in $O(\log k)$, giving $\Theta(N\log k)$ comparisons and a single
  sequential pass per merge.
- The number of passes is $1 + \lceil \log_k(N/M)\rceil$; larger fan-out $k$ cuts
  passes, but $k \lesssim M/B$ because every run needs a block-sized buffer in
  memory, else the merge starts seeking.
- **Replacement selection** forms initial runs of average length $\approx 2M$
  (double the naive bound), shrinking $N/M$ and often removing a whole pass.
- The same block-fan-out idea powers the [B-tree](/algorithms/data-structures/b-trees):
  packing $\Theta(B)$ keys per node makes search $\Theta(\log_B N)$ seeks instead
  of $\Theta(\log_2 N)$ — the same $\log_k$ savings applied to search.

[^skiena-ext]: **Skiena**, _The Algorithm Design Manual_, §4.6 — External Sorting. Merge sort adapts to disk by sorting memory-sized runs and merging them; replacement selection builds runs averaging twice the memory size.
[^clrs-ext]: **CLRS**, Problem 6-3 and Ch. 11 — heaps for $k$-way merging and the external-memory accounting in block transfers. The replacement-selection "snowplow" analysis gives expected run length $2M$.