The sort that is not an I/O problem: count the passes

Measure your machineNeeds Python with DuckDB

Problem

An external merge sort needs one merge pass as long as the number of sorted runs fits the merge's fan-in, M/B; with M = 500 MB of memory and B = 256 KB buffers, one pass can merge M²/B, about a terabyte. So sorting a few gigabytes with a few hundred megabytes of memory is not a multi-pass problem: it writes the data to disk once, reads it back once, and on a fast SSD the CPU work of comparing keys dominates.

Force DuckDB to sort with a small memory limit (memory_limit = 500MB) and watch the temporary files and CPU usage while it sorts 20 million rows of a random key with 100 bytes of padding into a new table. Try the same on a table already sorted by k. Then compute M²/B for these settings.

The question. How much temp space does the sort use, is it CPU- or I/O-bound, and does sorted input help?

Predict

With a 500 MB memory limit, does already-sorted input make DuckDB's 2 GB sort faster?

Much fasterAbout the sameSlower

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

the-sort-that-is-not-an.py51 linesDownload

View the code

the-sort-that-is-not-an.py

# /// script
# requires-python = ">=3.10"
# dependencies = ["duckdb"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""The sort that is not an external-sort problem.

DuckDB with memory_limit = 500 MB sorts 20 million rows of (random key, 100
bytes of padding), about 2.4 GB, and records the peak size of its temp files,
the time and the CPU time; then the same table already sorted by the key.
Finally the one-pass merge capacity M²/B for M = 500 MB and B = 256 KB.
"""
import argparse, json, os, resource, shutil, tempfile, threading, time
import duckdb

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--rows", type=int, default=20_000_000, help="Rows.")
p.add_argument("--memory-limit", default="500MB", help="DuckDB memory_limit.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()

tmp = tempfile.mkdtemp(prefix="duck_spill"); dbdir = tempfile.mkdtemp()
con = duckdb.connect(os.path.join(dbdir, "s.duckdb"))
con.execute(f"PRAGMA memory_limit='{args.memory_limit}'"); con.execute(f"PRAGMA temp_directory='{tmp}'")
con.execute(f"CREATE TABLE t AS SELECT random() AS k, repeat('x', 100) AS pad FROM range({args.rows})")
con.execute("CREATE TABLE t_sorted AS SELECT * FROM t ORDER BY k")
data_mb = con.execute("SELECT sum(length(pad) + 8) / 1048576 FROM t").fetchone()[0]
def watch(stop, peak):
    while not stop.is_set():
        peak[0] = max(peak[0], sum(os.path.getsize(os.path.join(d, f)) for d, _, fs in os.walk(tmp) for f in fs if os.path.exists(os.path.join(d, f))))
        time.sleep(0.05)
rows = []
for table in ("t", "t_sorted"):
    stop, peak = threading.Event(), [0]; th = threading.Thread(target=watch, args=(stop, peak)); th.start()
    c0 = resource.getrusage(resource.RUSAGE_SELF); t = time.perf_counter()
    con.execute(f"CREATE OR REPLACE TEMP TABLE out AS SELECT * FROM {table} ORDER BY k")   # the sorted result must be produced in full
    wall = time.perf_counter() - t; c1 = resource.getrusage(resource.RUSAGE_SELF); stop.set(); th.join()
    cpu = (c1.ru_utime - c0.ru_utime) + (c1.ru_stime - c0.ru_stime)
    rows.append({"input": "random order" if table == "t" else "already sorted", "seconds": wall, "cpu_s": cpu, "cpu_per_wall": cpu / wall,
                 "temp_peak_mb": peak[0] / 2**20})
M, B = 500 * 2**20, 256 * 2**10
summary = {"data_mb": data_mb, "one_pass_tb": M * M / B / 2**40, "fan_in": M // B}
for r in rows: print(f"{r['input']:<15} {r['seconds']:6.2f} s wall, {r['cpu_s']:6.2f} s CPU ({r['cpu_per_wall']:.1f} cores busy), temp files peaked at {r['temp_peak_mb']:,.0f} MB")
print(f"data ~{data_mb:,.0f} MB; one merge pass handles M²/B = {summary['one_pass_tb']:.2f} TB with fan-in {summary['fan_in']:,}")
con.close(); shutil.rmtree(tmp, ignore_errors=True); shutil.rmtree(dbdir, ignore_errors=True)

if args.json:
    with open(args.json, "w") as f:
        json.dump({"summary": summary, "tables": {"sorts": rows}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.
Terminal
```
uv run the-sort-that-is-not-an.py
uv run the-sort-that-is-not-an.py --help     # every knob
```

Knobs
Knob · default	What it changes
--rows20,000,000	Rows.
--memory-limit500MB	DuckDB memory_limit.

Our run

Sorting about 2 GB with 500 MB

Sorting about 2 GB with 500 MB
Input	Wall	CPU	Cores busy	Temp peak (MB)
random order	4.51 s	12.1 s	2.69	2.38K
already sorted	4.52 s	9.79 s	2.17	3.64K

Reference runApple M2 · 8 cores · 8 GB

Output · uv run the-sort-that-is-not-an.py

random order      4.51 s wall,  12.12 s CPU (2.7 cores busy), temp files peaked at 2,377 MB
already sorted    4.52 s wall,   9.79 s CPU (2.2 cores busy), temp files peaked at 3,643 MB
data ~2,060 MB; one merge pass handles M²/B = 0.95 TB with fan-in 2,000

macOS 26.6.2 · Python 3.13.3 · duckdb 1.5.6 · run 2026-10-20

What we found

Sorting about 2.06K MB of data, DuckDB's temp files peaked at 2.38K MB, close to the data size: one write and one read, as expected with a one-pass capacity of 0.954 TB. The sort kept 2.69 cores busy on average over 4.51 s. Already-sorted input took the same wall time (4.52 s) with less CPU, and wrote more temp data (3.64K MB), so presorting did not make the external sort cheaper here.

Read it

With today's memory sizes, an external sort of a dataset that fits on one disk needs one merge pass; the cost is one extra write and read of the data, not log-many. Whether it is CPU- or I/O-bound depends on the storage: on a laptop SSD, both matter, and neither is the multi-pass catastrophe the textbook case describes.