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
|