External and Practical Sorting: What Real Systems Do
What This Concept Is
A practical sorting decision starts with the API contract: ordering, stability,
mutation, memory, and failure behavior. The implementation's algorithm and hybrid
cutoffs can change with runtime version. Check official documentation and, when
necessary, the exact source revision. Do not infer an implementation from a name
such as qsort or transfer one language's stability guarantee to another.
External sorting addresses inputs larger than available working memory. Create sorted runs that fit the memory budget, then merge a bounded number of runs at a time. Count reads and writes for both run generation and merge passes.
Why It Matters Here
Asymptotically similar algorithms can have different memory and I/O costs. An engineer must account for record buffers, output buffers, key extraction, heap entries, open files, and the runtime itself. Allocating every byte of nominal RAM to a run leaves no space to sort or merge it.
Concrete Examples
Consider a synthetic 256 GB file and an 8 GB usable run budget after reserving overhead; units here are decimal. There are 32 initial runs. Run generation reads 256 GB and writes 256 GB. If buffers and open-file limits permit a single 32-way final merge, it reads and writes another 512 GB. Total transferred is 1,024 GB. At a stipulated sustained aggregate 0.5 GB/s, the ideal I/O-only time is 2,048 seconds, about 34.1 minutes. It excludes sorting CPU, seeks, contention, and startup. Counting only the final merge underestimates total traffic by half.
Let R=ceil(N/Mrun) runs and fan-in F>=2. Merge passes are ceil(log_F R) when R>1. In a materialized-pass model, each adds roughly 2N record transfers, plus the 2N for run generation. With F=8 and R=32, two merge passes are required. For R=1 no merge pass is needed. Streaming the last output to a consumer changes the write accounting and must be stated explicitly.
Common Confusion / Misconceptions
A fan-in such as sqrt(R) is not universally optimal. Buffer size, memory and file limits constrain it; storage characteristics determine the practical tradeoff. Measured speed ratios without a source, environment, and workload are not data. Stable in-memory runs are insufficient for globally stable merging unless ties between runs also preserve global input order or carry an original sequence key.
How To Use It
Write a sorting decision note with contract, candidate algorithms, representative inputs, peak-memory estimate, and measurement method. Python's documented stable sort supports repeated stable-key passes; confirm the chosen API in the official sources listed in resources. The course's iterator merge lab teaches one head per stream, not file buffering, crash recovery, or a complete external-sort service. Those are extensions with separate acceptance criteria.
Check Yourself
- Which pass was omitted if the example is estimated at 17 minutes?
- How many merge passes do 65 runs need at fan-in 8?
- Why is record count different from bytes when keys/payloads vary?
- How can independently stable runs lose global tie order?
Mini Drill or Application
Design a materialized external sort for a 100 GB input, 4 GB usable runs, and fan-in 5. Count runs, passes, transferred bytes, and buffer requirements. Then change the contract to a streamed final output and identify which cost disappears. Do not predict wall time without a stated throughput model. See P13.
Read This Only If Stuck
Use CLRS, Skiena, or Sedgewick and Wayne for external merging, sorting contracts, and practical resource accounting. These links open book indexes; find the named topic in your edition. Use the reading guide for the bounded assignment and worked examples before adding another source.