The Sorting Job That Times Out at Midnight
A school's reporting service must rank 200,000 students by a composite score each night. The developer first wrote a selection sort, which took 6 hours and missed the 2 a.m. deadline. They replaced it with a merge sort and the job now finishes in 4 seconds. A colleague proposes replacing merge sort with quicksort "because quicksort is faster on average." The dataset is built by concatenating 40 school exports, each of which arrives already sorted by student ID, and the composite score is strongly correlated with ID within each school. The service runs on a single core with 512 MB of RAM, and the full dataset is about 40 MB. The team also needs the top 20 students only, not a full ranking.
1. Explain the 6-hour to 4-second change using complexity analysis, and evaluate the colleague's quicksort proposal for this specific dataset.
Read the worked answer
Selection sort is O(n²): with n = 200,000, the comparison count is on the order of n²/2 ≈ 2 × 10¹⁰. Merge sort is O(n log n): about 200,000 × 17.6 ≈ 3.5 × 10⁶ comparisons, roughly four orders of magnitude fewer. A 6-hour job becoming a 4-second job is consistent with that ratio, and the constant factors (memory allocation, cache behaviour) do not change the asymptotic story at this scale.
The quicksort proposal is risky for this dataset specifically. Quicksort's average O(n log n) assumes reasonably random pivot behaviour. Here the input is 40 concatenated sorted runs, and score correlates with ID, so the data is highly structured. With a naive first-element or last-element pivot, each partition splits off a tiny piece and recursion depth approaches n, giving O(n²) behaviour and a real risk of stack exhaustion. Even with a median-of-three pivot, the concatenated runs create adversarial patterns.
The colleague's claim compares averages without checking the input distribution - the classic error of applying a complexity result outside its assumptions. If quicksort is wanted, the team should use a randomised or median-of-three pivot and test on the actual concatenated data. Otherwise merge sort's guaranteed O(n log n) and stable behaviour are the safer choice. Note also that merge sort needs O(n) auxiliary space; 40 MB of data fits comfortably in 512 MB, so that cost is acceptable here but would matter on a tighter machine.
2. The team only needs the top 20 students. Recommend an approach and justify it against simply sorting everything.
Read the worked answer
Sorting all 200,000 to read the first 20 is doing far more work than required. Two better options:
Option A - partial selection with a bounded heap. Maintain a min-heap of size 20 while streaming the records. Each new score is compared with the heap minimum; if larger, it replaces the root and the heap is reheapified in O(log 20). Total work is O(n log k) with k = 20, effectively linear, and memory is O(k) rather than O(n).
Option B - quickselect. Partition around a pivot until the top 20 are isolated; average O(n), but worst case O(n²) and the same structured-data pivot risk as quicksort.
Recommendation: Option A. It is streaming, so it does not require holding all 40 MB in memory at once, and its worst case is predictable - important for a nightly job with a hard deadline. It also composes well with the existing pipeline: records can be fed in as each school export arrives rather than concatenated first.
Justification against full sort. Full merge sort is O(n log n) ≈ 3.5 × 10⁶ comparisons and allocates an auxiliary array; the heap approach is roughly n comparisons plus small heap maintenance, with negligible memory. At 200,000 records the difference is seconds versus fractions of a second today, but the design also scales: if the dataset grows to 20 million, the full sort grows by a factor of about 100 while the heap approach grows roughly linearly with a fixed memory footprint.
The judgement is that the algorithm should match the output actually required. Choosing an algorithm for a problem you do not have (a full ranking) is a common and expensive mistake.