external sort
Sorting data too large to fit in memory by sorting it in memory-sized chunks written to disk, then merging the sorted chunks.
In more detail
Each chunk is sorted and saved to a temporary file; a k-way merge then reads one value at a time from each file and writes the combined output. Only k values need to be in memory at once. Databases and command-line tools such as sort use this for huge inputs.
Related terms
- k-way merge — Merging k sorted sequences into one by keeping the current front item of each in a min-heap and repeatedly taking the smallest.
- temporary file — A file or directory a script creates for its own scratch work and should delete before it finishes.
- heapq — Python's standard-library module of functions that treat an ordinary list as a binary min-heap.
- sorted merge — Combining two or more already sorted sequences into one sorted sequence by repeatedly taking the smallest front item.
Taught in
- Sorting In Real Systems: Stability, Keys And External Sort — Algorithms & Data Structures for Working Engineers