A sort produces a property, not an answer

What does an external sort really cost, and how does a distributed sort turn a global merge into a concatenation?

Sorting is the only operator here that computes nothing. It adds no information, removes no rows and changes no values. Its output is a permutation of its input. It exists for one purpose: to supply a physical property (order) that some other operator requires. That makes it the purest example of the idea that has run through this mechanism: operators are cheap; enforcers are the query; and sort is an enforcer with no operator attached.

Two consequences follow.

1. The best implementation of a sort is not running it. That is why "sort avoidance through interesting orders" is not the last item in this article but its conclusion.
2. Because sorting computes nothing, its cost depends on nothing semantic. A join's cost depends on key frequencies. An aggregation's cost depends on NDV. These are the two least reliable statistics in any catalogue. A sort's cost depends only on N (data size), M (memory) and B (I/O block size). It is the only operator here whose cost you can compute in advance and be right. A plan with a sort is boring, and boring is the scarcest property in query execution.

---

The core tension: amortization across requirements

Hash gives you co-location (equal keys end up together) at linear cost and leaves nothing behind. Sort gives you co-location and order, at a log factor, and the order composes: one enforcement can satisfy a merge join, then an aggregation, then an ORDER BY.

So the trade is not "which algorithm is faster". It is amortization across requirements:

• One consumer of the order: hash wins on even terms.
• Three consumers: hash pays three times, while sort paid once.

Extend the count from "operators in this query" to "all future queries", and you get clustering, bucketing, LSM ordering (the sorted files of a log-structured merge tree) and indexes. It is the same arithmetic with a much larger base, paid at write time. This is where physical design either collects on its investment or finds that it bought the wrong order.

---

External merge sort: not a log problem

An external sort sorts data larger than memory. It has two phases.

1. Run generation. Fill M bytes of memory, sort them in place, write the sorted block (a run) to disk. Repeat. This produces N/M runs.
2. Merge. Read one block from each of F runs, merge them, and write the output. F is bounded by memory divided by block size: F = M/B, because each input run needs a buffer of one block, and the output needs one too.

The number of passes over the data is 1 + ⌈log_F(N/M)⌉. A single merge pass is enough when N/M ≤ F, which means

Worked examples

(Check the second line: 16 GB / 8 MB = 2,000, so 16 GB × 2,000 = 32,000 GB = 32 TB.) In a distributed sort each node handles only N/P, so the per-node input is smaller again.

The honest statement about external sorting is therefore: the logarithm is a constant 2, and it has been 2 for thirty years, because memory M and block size B grew together. External sort is not a complexity problem. It is a bandwidth problem of exactly 4N: read N, write N as runs, read N, write N as output. Discussions of its asymptotics discuss a term that never changes.

Where it does change: the block size. On object storage (cloud storage where each request has a latency of tens of milliseconds and a price), B must be 8 to 16 MB to amortize the per-request fixed cost. A larger B reduces the fan-in F for the same memory, which lowers M²/B and brings the third pass closer. The fixed cost of an I/O operation determines the block size; the block size determines the fan-in; the fan-in determines the number of passes.

Two corrections to the standard account

Fan-in should not be maximized. An F-way merge costs about log₂ F comparisons per record in the merge phase. With F = 1,000 that is about ten comparisons per record, comparable to the entire in-memory sort's per-record cost. Raising the fan-in to remove a pass saves I/O but spends CPU. The optimum is not at the maximum. (A loser tree, a tournament structure for picking the next smallest record, improves the constant but not the log.)

Replacement selection is a correct optimization for a cost model that no longer binds. Replacement selection keeps a heap in memory and emits the smallest key that is not smaller than the last key emitted. On random input it makes runs of average length 2M instead of M, which halves the number of runs. But it destroys sequential locality: a heap of M elements is a random-access structure, whereas a modern in-memory sort is cache-friendly and can use vector instructions. And halving the number of runs almost never changes a pass count that is already two. Engines mostly abandoned it, correctly. What survives is its adaptive property: on nearly-sorted input it produces arbitrarily long runs, and the sort collapses toward a single pass. The technique is obsolete as a general optimization and alive as an adaptivity mechanism. Remember this whenever an old algorithm looks replaced.

The bottleneck moved

With a 4N I/O budget against NVMe drives that deliver several GB/s, and in-memory comparison sorting of string keys with collation (language-aware ordering rules) running at tens of MB/s per core, a sort is now often CPU-bound instead of I/O-bound. This is the reverse of the picture in every textbook that teaches the pass formula. That inversion is the reason for the section on normalized keys below.

---

Sample-based range-partitioned sort

A distributed sort must produce a global order across P machines. There are two shapes.

1. Sort locally, then merge globally. The global merge either goes through one node or pushes all data through a merge tree.
2. Range-partition first, then sort locally. Each record goes to the machine that owns its key range. Each machine sorts its share. The global result is the concatenation of the parts.

The second wins for a structural reason: range partitioning turns a global merge into a concatenation. Hash partitioning cannot do this. Hash gives co-location without order, so the parts do not compose. This is the sharpest demonstration that hashing and ordering are not two interchangeable ways to group things: one produces a result that composes and the other does not.

Choosing the splitters

The difficulty is choosing the splitters (the key values that divide the ranges). Equal partitions need knowledge of the key distribution, and knowing it needs reading the data. The solution is to sample: draw s records, sort the sample, and take its quantiles as splitters.

• The sample size needed to keep partition imbalance within a factor (1+ε) grows roughly like P/ε². Tightening the balance tolerance is quadratically expensive in sample size, the same square-root law as before. In practice, a few hundred samples per partition is the working rule.
• This is the standard case of randomization replaces coordination. Exact splitters would need a full pass and a global reduction. A random sample replaces that coordination entirely and pays with a bounded imbalance.

Three failure modes

1. Range partitioning does not fix skew. It fixes distributional skew, a key space where values cluster unevenly, because splitters can be placed densely where the data is dense. It does nothing for a point mass. If one key occurs more than N/P times, no splitters can balance the partitions: a splitter can only fall between distinct values, and one value is an atom of the partitioning. This is the same dead end that hash partitioning reached in the join article, approached from the other side. "Switch to range partitioning" is not an answer to a hot key.

2. A biased sample gives correct-looking splitters and a broken sort. If the input is already ordered (time-partitioned files read in order are the normal case), then taking the first s records samples one end of the key space. All splitters are wrong in the same direction. The failure is a badly unbalanced sort, not an error message. Systematic or random sampling is not a refinement here; it is the correctness condition.

3. Sampling introduces a barrier. The partition boundaries must exist before any record can be routed. A distributed sort is therefore at least two passes over the data (or one pass over a sampled subset plus one full pass), and the second cannot start before the first ends. This is the same structural cost that sideways information passing paid in the join article: converting independent work into dependent work.