Algorithms and Data Structures · Senior · Question 19 of 75
How do you sort a 200 GB file on a machine with 8 GB of RAM?
- 1Split it by first character and sort each file separately
- ✓Correct answer: Sort chunks that fit in memory, then k-way merge them with a heap
- 3Load it with memory-mapped I/O and call a normal sort
Explanation
External merge sort writes sorted runs to disk and then merges them, reading each run sequentially. The heap picks the smallest head among k runs in O(log k). Splitting by first character doesn't balance the pieces.