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

Taught in

References