[prev] 68 [next]

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)