[prev] 69 [next]

Cost of n-Way Merge Sort (cont)

Generalising from previous example ...

For b data pages and B buffers

  • first pass: read/writes b pages, gives b0 = ceil(b/B) runs
  • then need ceil(lognb0) passes until sorted, where n = B-1
  • each pass reads and writes b pages   (i.e. 2.b page accesses)

Cost = 2.b.(1 + ceil(lognb0)),   where b0 and n are defined above