[prev] 15 [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 produces 18 × 240-page sorted runs
  • pass 2 produces 2 × 3600-page sorted run
  • pass 3 produces 1 × 4096-page sorted run
(cf. two-way merge sort which needs 11 passes)

For b data pages and n=15 input buffers (15-way merge)

  • first pass: read/writes b pages, gives b0 = ceil(b/B) runs
  • then need ceil(lognb0) passes until sorted
  • each pass reads and writes b pages (2.b )
Cost = 2.b.(1 + ceil(lognb0)),   where b0 = ceil(b/B)