Consider a disk with average seek time of 10 ms, average rotational latency of 5 ms, and a transfertime of 1 ms for a 4KB block. The cost of reading/writing a block is the sum of these values (i.e. 16 ms).We are asked to sort a large relation consisting of 10,000,000 blocks of 4KB each. For this, we use a computer on which the main memory available for buffering is 320 blocks (a bit small memory).

 

We begin as usual by creating sorted runs of 320 blocks each in phase 1. Then, we do 319-way merges  .Determine the number of phases needed, and evaluate the cost of the Multi Phase Multiway MergeSort.We start by creating sorted sublists. We fill in the main memory (MM) with 320 blocks, sort them inMM and write the sorted sublist to disk (phase one).Next we need to do merge. However, the number of sorted sublists is too big to allow a merge withonly one pass. Since we need an output buffer, we can only merge 319 sorted sublists at a time.Therefore, we end up again with sorted sublists, but fewer this time. These sublists need to be mergedin turn. Find the number of sublists at each phase. Find the total number of I/Os