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