Referring to the 9th page of a slide, when we use multi-pass multi-way external merge sort on a file with $N$ pages using $B$ buffer pages, in "pass 0" we'll read a chunk of $B$ pages into all buffers, sort the chunk, and write it back to disk, repeatedly to produce $\lceil{N/B}\rceil$ sorted chunks. In later passes, we'll use $(B-1)$ buffers for input and the last buffer for output to merge $(B-1)$ sorted chunks together each time each pass.

As is not mentioned at all, how the whole chunk (in pass 0) can be sorted when all buffers are being used for input?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.