Choosing a Sorting Strategy for Streaming Sensor Data
A weather station logs 2,000,000 temperature readings per day. Each reading is a 64-bit float with a timestamp. The station must produce two outputs: (1) a daily report sorted by temperature, and (2) a running median updated after every reading for a live display. The station has 512 MB of RAM and the readings for one day occupy about 16 MB. A developer proposes loading all readings into an array and using merge sort for the report, and using the same full-array sort after each new reading to update the median. On a test day, the report completes in 1.4 seconds, but the live display lags by many seconds. The developer also notes that on a second station with only 64 MB of RAM, a different approach was needed for a 40-day archive.
1. Analyse the time complexity of the developer's two uses of merge sort and explain why the live display lags.
Read the worked answer
Merge sort on n readings is O(n log n). For the daily report with n = 2,000,000, that is about 2e6 × 21 ≈ 4.2e7 comparisons, which matches the observed 1.4 seconds - acceptable.
The live display is different. After each new reading, the developer re-sorts the entire array, which costs O(n log n) per update. Over n readings the total is O(n² log n). With n = 2,000,000 this is astronomically large: even the final single sort alone costs 4.2e7 operations, and doing it 2e6 times gives roughly 8.4e13 comparison-level operations. That is why the display lags by seconds and worsens as the day progresses - each update is more expensive than the last because n grows.
The mistake is failing to distinguish a one-off sort from a repeated-update workload. The report genuinely needs one O(n log n) sort. The median does not need a full sort at all; re-sorting is the wrong tool for a streaming statistic.
2. Propose a better data structure for the running median and justify its complexity.
Read the worked answer
Maintain two heaps: a max-heap holding the lower half of readings and a min-heap holding the upper half, kept balanced so their sizes differ by at most one. The median is the top of the larger heap (odd count) or the average of the two tops (even count).
Insertion: push the new reading onto one heap (O(log n)), then rebalance by moving at most one element between heaps (O(log n)). Each update is therefore O(log n), and n updates cost O(n log n) total - the same order as a single sort but spread across the stream, so the display updates instantly.
Memory: two heaps store n elements total, about 16 MB for a day's data, well within 512 MB. This is a strict improvement over re-sorting: O(log n) per update versus O(n log n) per update. The key insight is that the median depends only on the boundary between the lower and upper halves, not on the full ordering, so a partial-order structure (heaps) suffices. This is the judgement the question tests: match the data structure to the query, not to the data volume.
3. Explain how the 64 MB station should handle the 40-day archive and why the in-memory approach fails there.
Read the worked answer
Forty days at 16 MB per day is about 640 MB of readings, ten times the 64 MB RAM. Loading everything into memory is impossible, so an in-memory sort or heap cannot hold the full archive. The station must use external sorting.
Approach: read the archive in chunks that fit comfortably in RAM (say 32 MB, leaving room for overhead), sort each chunk in memory with merge sort, and write each sorted chunk (a 'run') to disk. Then perform a k-way merge of the runs using a min-heap of size k, streaming the merged output to disk. Total I/O is O(N log(N/M)) where N is total records and M is the chunk size, and the merge itself is O(N log k). Memory stays bounded by the chunk size plus the heap of k run-heads.
Why the in-memory approach fails: it requires O(N) memory, which exceeds the 64 MB budget by an order of magnitude, causing thrashing or outright failure. The lesson is that complexity analysis must include space, not just time. The 512 MB station could hold a day in memory; the 64 MB station cannot hold 40 days, so the algorithm must be redesigned around the memory hierarchy rather than scaled up.