Let's say I have a disk with an average seek time of 10ms, an average rotational latency of 5ms and a transfer time of 1ms for a 4kb block and the cost of reading the block is the sum of these values. If I have to sort a large relation consisting of 10,000,000 blocks of 4kb each and I have 320 blocks of main memory available for buffering then how would I determine the cost of this multi phase multiway merge sort. I know that in the first phase you need to create sorted runs of 320 blocks each then do 319-way merges. Also because of the small memory, this would usually be in 2 phases but here it will turn into 3 phases.

I also know that the number of sorted sublists is 10,000,000/320 = 31,250 but I'm not sure where to go from here to determine the cost.

  • $\begingroup$ I'm not sure if this is related to your algorithm, but the number of I/O's required for a well known I/O-efficient merge-sort algorithm is $O((n/B) \log_{M/B}(n/B))$ (see e.g. here), where $n$ is the input size, $M$ is the internal memory size and $B$ the block size. $\endgroup$ – Discrete lizard Mar 31 '17 at 17:04
  • $\begingroup$ I'm not sure if that could work but I've never learned how to do something like that so I'm not sure. All I know is that because only 320 blocks can fit into the main memory at a time, you'd have to fill the main memory 31,250 times. Then I think you do something regarding the average time it takes to read a block. $\endgroup$ – david mah Apr 4 '17 at 15:22
  • $\begingroup$ Does the seek time on the disk that depend on the distance of the subsequent blocks in memory? If so, the running time I gave isn't directly applicable, as it doesn't take that into account. (The fact that you need an exact value and not an asymptotic bound also means it isn't that useful). $\endgroup$ – Discrete lizard Apr 5 '17 at 9:27
  • $\begingroup$ Since you apparently know how this 'multi phase multiway merge sort' algorithm works, I don't see where you're stuck. Could you perhaps explain how this algorithm works or a link to its description? $\endgroup$ – Discrete lizard Apr 5 '17 at 9:28

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.