External Sorting

Read a memory-sized chunk, sort it internally, and write it as a sorted run; repeat for the entire file. Then repeatedly merge runs using buffered input and output until one final sorted file remains.

A k-way merge combines k runs in one pass using one buffer per run and a size-k heap. Increasing k reduces merge levels from roughly log₂r to log_kr, at the cost of more buffers and heap work.

Disks and storage systems transfer large sequential blocks efficiently, while random seeks and scattered reads have high latency. External merge sort therefore streams each run rather than performing random-access comparisons across the file.