Overview
External Sort breaks a large input into memory-sized runs, sorts each run, writes it out, and performs one or more merge passes.
ExtendedSource checked
External Sort
Sorts data sets that are too large to fit in memory by sorting chunks and merging them from disk.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Sorting
- Difficulty
- Advanced
- Family
- External Memory Sorting
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 1
- Code example
- Ready
- Visualization
- Ready
Core Concepts
external memorysorted runsmulti-way mergebuffer management
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(M) memory plus disk runs
When to Use
- Use when the data is larger than memory but can be processed in sequential passes.
- Use when sorting large log files is a central requirement.
When Not to Use
- Avoid when low-latency in-memory sorting is enough.
- Avoid when the data fits in memory and a normal in-memory sort is simpler.
What It Does
- Splits input into sorted runs
- Merges runs with bounded memory
- Trades CPU work for controlled disk access
Use Cases
- Sorting large log files
- Building database indexes
- Processing data lake exports
Inputs
- Large file or stream
- Available memory limit
- Comparison or key function
Outputs
- Sorted file or stream
Pseudocode
- 1.Read a chunk that fits in memory
- 2.Sort the chunk and write it as a run
- 3.Open several runs at a time
- 4.Repeatedly merge the smallest next value until one sorted output remains
Canonical Example
- Input
- chunks = [[7, 2], [5, 1], [4, 3]]
- Output
- sorted = [1, 2, 3, 4, 5, 7]
- Explanation
- Each chunk is sorted locally, then the sorted runs are merged into one ordered output.
Implementation Notes
- Use a priority queue for the next item from each open run.
- Keep runs, buffers, and merge fan-in explicit so memory use stays predictable.
- Keep a tiny example with expected output beside the implementation.
Common Pitfalls
- Choosing too many merge inputs can exhaust file handles or shrink buffers too much.
- Underestimating I/O cost can dominate the runtime even when comparisons are efficient.
- Not defining boundary, empty, or degenerate inputs before implementation.
Interactive Mechanism Walkthrough
Array Partition & Ordering TraceShow disk-backed sorted runs feeding a multi-way merge buffer.
38[0]
14[1]
52[2]
23[3]
61[4]
19[5]
44[6]
29[7]
Step 1 of 4: Read a chunk that fits in memory
array-sortNotes
Real performance depends heavily on sequential I/O, buffer sizes, and merge fan-in.
Sources (2)
What each reference supports for this entry.
The Art of Computer Programming, Volume 3
BookSorting and searching reference for external-memory sorting, run generation, and multiway merging.
NIST DADS: External Sort
EncyclopediaDictionary reference for external sorting over disk or tape memory and its relationship to external-memory algorithms.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsesMerge Sort
External sorting commonly creates sorted runs and merges them with merge-sort-style passes.
Related Algorithms
Tags
SortingExternal MemoryDivide and Conquer