Choosing a Sort Routine Under a Hard Memory Cap: Crossover Points and Workloads
A team is choosing between two internal sorting routines for a log-processing service. Routine M is a merge sort: about 4n log2 n key comparisons and an auxiliary buffer of 8n bytes. Routine I is an insertion sort: about n²/4 comparisons on random input and no extra memory beyond a few registers. The machine executes roughly 10⁸ comparisons per second when data fit in cache. Two workloads are in scope: (i) a nightly batch of 10⁶ records that must finish inside a 2-second window; and (ii) repeated re-sorting of small, nearly sorted arrays of 40–80 records arriving continuously from a sensor, where the order is typically off by only a handful of adjacent swaps. The service runs in a container capped at 4 MB of RAM for the sorting step. The team lead argues that routine I is 'obviously better' because it is in-place, and proposes deleting routine M.
1. Evaluate both routines for workload (i) at n = 10⁶, considering time and the 4 MB cap. What is the correct engineering conclusion?
Read the worked answer
Time. Routine M: 4 × 10⁶ × log2(10⁶) = 4 × 10⁶ × 20 = 8 × 10⁷ comparisons, about 0.8 s at 10⁸/s - inside the 2-second window. Routine I: n²/4 = 2.5 × 10¹¹ comparisons, about 2,500 s - three orders of magnitude over budget. Routine I fails workload (i) outright.
Memory. M's buffer is 8n = 8 MB, double the 4 MB cap, so M as specified does not run either. The fix is bounded-buffer merging: sort chunks of about 4 × 10⁵ records in memory (3.2 MB), spill sorted runs, then k-way merge with small read buffers. That introduces I/O, so the 0.8 s compute figure is optimistic and the 2-second window must be re-verified against disk or tmpfs throughput.
Conclusion: keep M and re-engineer its memory. Deleting M - as the team lead proposes - makes workload (i) impossible. The in-place property of I is worthless when the algorithm cannot finish within a day.
2. For workload (ii), does the same answer hold? Compute the crossover for random data and explain why it is the wrong threshold for nearly sorted input.
Read the worked answer
Random-data crossover: set 4n log2 n = n²/4, giving n = 16 log2 n. At n = 64: M = 4 × 64 × 6 = 1,536 comparisons, I = 64²/4 = 1,024 - insertion wins. At n = 128: M = 4 × 128 × 7 = 3,584, I = 128²/4 = 4,096 - merge wins. The crossover lies between 64 and 128.
Why that threshold is wrong here: workload (ii) is not random. Arrays of 40–80 records with a handful of adjacent swaps are nearly sorted, and insertion sort then costs about n plus the number of inversions - roughly 40 to 90 comparisons, not n²/4. At n = 80 that is an order of magnitude below M's roughly 1,300 comparisons, with no allocation and better cache behaviour.
Verdict: I is clearly correct for (ii), M for (i); deleting either breaks a workload. The proper answer is a hybrid - insertion sort for runs below the measured crossover, merge for the rest, which is exactly why production sorts use a small-run cutoff tuned empirically rather than one asymptotic winner.
3. Identify the flaw in the team lead's reasoning and describe how you would settle the choice empirically, including what the comparison counts ignore.
Read the worked answer
The flaw: treating an asymptotic property (O(1) extra memory) as decisive without checking which constraint actually binds. In workload (ii) memory is not scarce - a few hundred bytes - so in-place buys nothing and comparisons dominate. In workload (i) memory is scarce, but the remedy is bounded-buffer external merge, not a quadratic algorithm; 2,500 s is not a trade-off, it is a failure.
Settling it empirically: benchmark on the real input distribution, counting comparisons, cache misses and allocations rather than raw operation counts. Measure the crossover directly, because constants - branch prediction, cache-line size, copy speed - are exactly what asymptotic notation discards.
What the counts ignore: stability (does the log ordering need ties preserved?), worst-case behaviour on adversarial or adversarial-ish input, and whether the 4 MB limit is a hard container cap or a soft target. If it is hard, the sort's memory must be an explicit line item in the design review, and the external-merge path must be tested under peak load, not assumed from the 0.8 s compute estimate.