[prev] 7 [next]

Non-recursive Mergesort

Recursive algorithm described top-down, but works bottom-up

Explicit bottom-up mergesort:

  • on each pass, array contains sorted runs of length m
  • at start, treat as N sorted runs of length 1
  • 1st pass merges adjacent elements into runs of length 2
  • 2nd pass merges adjacent 2-runs into runs of length 4
  • continue until a single sorted run of length N
This approach is used for sorting disk files.