External Mergesort (cont)
External mergesort basic idea:
- have two files, A and B, which alternate as input/output
- scan input, sorting adjacent pairs, write to output
- scan input, merging pairs to sorted runs of length 4
- scan input, merging pairs to sorted runs of length 8
- repeat until entire file is sorted
How many iterations are needed?
- double scan length until ≥ file size (N
Item s)
- #iterations = ceil( log2N )
|