Menu
I'm looking for an answer to this question that comes from a class on data structures and algorithms. I learned about the merge sort but don't remember clusters and buffers. I'm not quite sure I understand the question. Can someone help explain or answer it?
A file of size 1 Million clusters is to be sorted using 128 input buffers of one cluster size. There is an output buffer of one cluster size. How many Disk I/O's will be needed if the balanced k-way merge sort (a multi-step merge) algorithm is used?
217
While we know that it is challenging to learn data structure, programmers need certain support and guidance whenever they get stuck in problem-solving. Lack of support is also one of the reasons programmers don't know the best way to learn data structures and algorithms.
It is asking about the total number of disk operations, a cluster here can be any size.
You need to know how many Disk IOs are needed per iteration of a balanced k-way merge sort. (hint: every merge pass requires reading and writing every value in the array from and to disk once)
Then you work out how many iterations must be performed to read your data.
The total number of Disk IOs can then be calculated.
87
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
