This is a beta course, so its structure, chapters, and examples may continue to change.
External Sorting
External sorting handles data too large for memory, using external storage (disk). Split the big file into memory-fit chunks, sort each, then multiway-merge.
Click "Step forward" to watch the algorithm state change.
Multiway merge sort
- Split into chunks, load each into memory and sort (e.g., merge sort).
- Merge sorted chunks (“runs”) via multiway merge.
- Use 2-way, 4-way, or multiway merging to reduce passes.
- Large DBs, search logs, big-data analytics
- Any sort where the whole dataset cannot fit in memory
- Sorting phase: (per chunk)
- Merge phase: , = merge ways
- Overall:
- Space: dominated by disk I/O and buffer sizes
Exercise 1
Describe the basic flow and use cases of external sorting.
Approach: Sort in chunks plus multi-way merging, which suits very large data.
Steps:
- Sort the chunks in memory and generate sorted runs
- Merge the runs in multi-way fashion into the final file
- Applies when the data no longer fits in memory
Answer: Chunked sorting plus merging, which suits sorting very large data.
Exercise 2
Common merge ways and their complexity?
Approach: Two-way and multi-way merging, and their complexity.
Steps:
- Two-way, four-way and multi-way merging
- Complexity , where is the number of ways
Answer: Multi-way merging is commonly used, with complexity .