Algorithms for External Sorting
External sorting: refers to sorting algorithms
that are suitable for large files of records stored on disk that do not fit
entirely in main memory, such as most database files.
Sort-Merge strategy:
starts by sorting small subfiles (runs) of the main file and then
merges the sorted runs, creating larger sorted subfiles that are merged in turn.
–Sorting phase: nR = ⌐(b/nB)¬
–Merging phase: dM = Min (nB-1, nR); nP = ⌐(logdM(nR))¬
nR: number of initial runs; b: number of file
blocks;
nB: available buffer space; dM: degree of merging;
nP: number of passes.
 |
Outline of the short merge algorithm for external sorting |
No comments:
Post a Comment