External Sorting
Learn External Sorting (Sorting, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Sorting Data That Doesn't Fit in Memory External sort handles datasets LARGER than available RAM (e.g. a 100GB file with 16GB of memory) - the classic technique is External Merge Sort : Phase 1 (chunk & sort): read a memory-sized chunk, sort it in RAM (any in-memory sort), write it back to disk as a sorted "run". Phase 2 (merge): repeatedly K-way merge the sorted runs (using a min-heap, same idea as Merge K Sorted Lists) until only one fully-sorted file remains.