[prev] 78 [next]

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 Items)
  • #iterations = ceil( log2N )