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.
|