What if the array won’t fit in RAM? You can’t just call sort(). External merge sort handles it in two phases. First, read the data in chunks small enough to fit in memory, sort each chunk, and write it back to disk as a sorted run. Second, k-way merge all the runs at once: keep a pointer into each, and repeatedly emit the smallest value among the current heads. Only a tiny window of each run is ever in memory. Run both phases and watch a dataset far larger than the buffer come out fully sorted.
O(n log n) comparisons · O(n/B) disk I/O · memory holds only one block per run
run
A chunk of data that was small enough to sort in memory, written back sorted.
memory buffer
The limited RAM — holds one chunk to sort, then one block of each run to merge.
k-way merge
Merge all runs at once by repeatedly taking the smallest current head.
streaming
Output is produced incrementally; the full data is never all in memory at once.
extsort.js — make runs, then merge them
Ready
12 numbers, but memory holds only 4 at a time. Phase 1: load 4, sort them in memory, write a sorted run to disk — repeat. Step to begin.
runs
phase
0
runs
0
sorted out
How it works
The insight is that merging is streaming-friendly: to produce the next smallest element of a merged output, you only need to see the current front of each sorted run — not the whole run. So during the merge phase, memory holds just one block from each of the k runs at a time, no matter how large the runs are. That’s why external merge sort scales to data far bigger than RAM while keeping disk I/O sequential (a few passes over the data) rather than random.
1
Phase 1 — make sorted runs
Read as much data as fits in memory, sort it there with a normal in-memory sort, and write it back to disk as a sorted run. Repeat until all input is consumed into runs.
2
Phase 2 — open all runs
Put a read pointer at the start of each sorted run. Only the current head of each run needs to be in memory — one block per run.
3
Emit the smallest head
Compare the heads of all runs, emit the smallest to the output, and advance that run’s pointer. A min-heap makes picking the smallest of k heads efficient.
✓
Repeat until all runs drain
Keep emitting the smallest head until every run is exhausted. The output is fully sorted, and memory never held more than one block per run at a time.
Comparisons
O(n log n)
Disk I/O
sequential
Memory
one block / run
Used in
databases, ETL
The code
# Phase 1: create sorted runs that fit in memory
runs = []
while chunk := read(input, MEMORY_SIZE):
runs.append(write_run(sorted(chunk))) # sort in RAM, spill to disk# Phase 2: k-way merge with a min-heap of run heads
heap = [(peek(r), r) for r in runs]; heapify(heap)
while heap:
val, r = heappop(heap)
emit(val) # smallest current head
nxt = advance(r)
if nxt isnotNone: heappush(heap, (nxt, r))
Quick check
1. Why does external merge sort split into runs first?
The whole dataset can’t fit in RAM, so you sort it in pieces that do (the runs), write them back, and then merge the sorted runs — which can be done with only a small window of each in memory.
2. During the merge phase, how much of each run must be in memory?
To emit the next smallest element you only need to compare the current heads of the runs. So merging needs only one block per run in memory, which is why the method scales past RAM.
3. What keeps disk I/O efficient in external merge sort?
Both phases stream data sequentially: runs are written and then read front-to-back. Sequential disk I/O is far faster than random seeks, which is the whole reason this beats trying to random-access-sort on disk.
FAQ
What is external merge sort?
A sort for data too large for memory. Phase one reads memory-sized chunks, sorts each, and writes sorted runs; phase two k-way merges the runs, keeping only each run’s current head in memory. It sorts arbitrarily large data with bounded memory and sequential disk I/O.
What is a k-way merge?
Merging k already-sorted lists into one at once: keep a pointer into each and repeatedly emit the smallest among the current heads, using a min-heap to find it in O(log k) per element. It generalizes the two-way merge in ordinary merge sort.
How much memory does external merge sort need?
Enough to sort one chunk in phase one, and in phase two one block per run plus an output buffer. More memory means larger runs and a higher merge fan-in, reducing passes over the data. The number of passes is classically expressed in terms of memory M and block size B.
Where is external merge sort used?
Databases (sorting query results, building indexes beyond memory), big-data frameworks (the shuffle/sort in MapReduce, Spark, Hadoop), and tools like the Unix sort utility on files larger than RAM — the standard approach whenever the data exceeds memory.