Cost of n-Way Merge Sort
Consider file where b = 4096, B = 16 total buffers:
- pass 0 produces 256 × 16-page sorted runs
- pass 1
- performs 15-way merge of groups of 16-page sorted runs
- produces 18 × 240-page sorted runs (17 full runs, 1 short run)
- pass 2
- performs 15-way merge of groups of 240-page sorted runs
- produces 2 × 3600-page sorted runs (1 full run, 1 short run)
- pass 3
- performs 15-way merge of groups of 3600-page sorted runs
- produces 1 × 4096-page sorted runs
(cf. two-way merge sort which needs 11 passes)
|