[prev] 62 [next]

Non-recursive Mergesort

Non-recursive mergesort does not require a stack
  • partition boundaries can be computed iteratively
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.