What is External Sorting?
Learn what external sorting is, how external merge sort and k-way merging work, and how to answer this interview question well.
Expected Interview Answer
External sorting is a family of algorithms for sorting data too large to fit in main memory, most commonly external merge sort: split the data into memory-sized chunks, sort each chunk in memory, write it to disk as a sorted run, then repeatedly merge sorted runs using a small in-memory buffer until one fully sorted file remains.
The core insight is that disk (or network) I/O, not CPU comparisons, is the bottleneck, so the algorithm is designed to minimize the number of passes over the data rather than minimize comparisons. In the run-generation phase, the input is read in blocks that fit in RAM, sorted with an in-memory algorithm like quicksort, and written back out as sorted runs. In the merge phase, a k-way merge reads a small buffer from each of k runs simultaneously and repeatedly outputs the smallest buffered element, refilling buffers as they empty, which needs only O(n/B) I/O operations per pass where B is the block size. Increasing the merge fan-in k reduces the number of passes needed, which is why external sort implementations tune k based on available memory. This same idea underlies distributed sorting systems and database ORDER BY operations on datasets larger than RAM.
- Sorts datasets far larger than available RAM
- Minimizes expensive disk I/O passes, not just comparisons
- K-way merging reduces total passes over the data
- Foundation for database sort operators and distributed sort systems
AI Mentor Explanation
External sorting is like organizing a decade's worth of scorecards that cannot all fit on one desk at once. A scorer sorts each stack that does fit on the desk by date, writes each sorted stack back into a labeled box, then combines boxes by comparing only the topmost visible card from each box and pulling the earliest one repeatedly until all boxes are merged into one ordered stack. Only a handful of cards from each box need to be visible on the desk at any time, never the whole decade at once. This two-phase approach — sort what fits, then merge the sorted pieces using minimal desk space — is exactly how external merge sort handles data too big for memory.
Step-by-Step Explanation
Step 1
Split into memory-sized runs
Read blocks of data that fit in RAM, sort each with an in-memory algorithm, and write out as sorted runs.
Step 2
Open buffered readers per run
For a k-way merge, keep a small in-memory buffer of the next unread elements from each of k sorted runs.
Step 3
Repeatedly output the minimum
Compare the buffered heads across all k runs, output the smallest, and refill that run's buffer from disk as needed.
Step 4
Merge in passes until one run remains
If more runs exist than fit in one merge fan-in, merge in multiple passes, reducing pass count by increasing k.
What Interviewer Expects
- Explain the two phases: run generation, then k-way merge
- State that disk I/O, not CPU comparisons, is the bottleneck being minimized
- Explain how a min-heap enables efficient k-way merging
- Connect external sort to real systems: database ORDER BY, distributed sort, sort-merge join
Common Mistakes
- Trying to load the entire dataset into memory and sort with quicksort directly
- Forgetting that increasing merge fan-in k reduces the number of I/O passes
- Not mentioning a min-heap as the natural structure for efficient k-way merging
- Confusing external sorting with simply sorting a file that happens to be on disk but fits in RAM
Best Answer (HR Friendly)
“External sorting is how you sort data that is too big to fit in memory all at once, like a massive database table. I would explain it works in two steps: first sort small chunks that do fit in memory and save them to disk, then merge those sorted chunks together using very little memory at a time.”
Code Example
import heapq
def create_sorted_runs(input_path, run_size, run_paths):
with open(input_path) as f:
while True:
lines = [f.readline() for _ in range(run_size)]
lines = [x for x in lines if x]
if not lines:
break
lines.sort(key=lambda x: int(x.strip()))
run_path = f"run_{len(run_paths)}.txt"
with open(run_path, "w") as out:
out.writelines(lines)
run_paths.append(run_path)
def merge_sorted_runs(run_paths, output_path):
files = [open(p) for p in run_paths]
heap = []
for i, f in enumerate(files):
line = f.readline()
if line:
heapq.heappush(heap, (int(line.strip()), i))
with open(output_path, "w") as out:
while heap:
value, i = heapq.heappop(heap)
out.write(f"{value}\n")
line = files[i].readline()
if line:
heapq.heappush(heap, (int(line.strip()), i))
for f in files:
f.close()Follow-up Questions
- How would you choose the run size when memory is limited?
- Why is a min-heap the right structure for a k-way merge?
- How does external sorting relate to a database sort-merge join?
- How would you extend this to sort data distributed across multiple machines?
MCQ Practice
1. What is the primary resource external sorting algorithms optimize for?
External sorting minimizes disk (or network) I/O passes, since I/O is far more expensive than in-memory comparisons for data that does not fit in RAM.
2. What data structure most naturally supports an efficient k-way merge?
A min-heap holding one buffered element per run gives O(log k) selection of the next smallest element across all k runs.
3. What is the first phase of external merge sort?
External merge sort first splits the input into memory-sized chunks, sorts each in memory, and writes each out as a sorted run before merging.
Flash Cards
What problem does external sorting solve? — Sorting datasets too large to fit in main memory.
What are the two phases of external merge sort? — Run generation (sort memory-sized chunks) then k-way merge of the sorted runs.
What resource does external sorting minimize? — Disk I/O passes over the data, not just comparisons.
What structure enables an efficient k-way merge? — A min-heap holding the next buffered element from each run.