CODEWITHSUNDEEP
data-structures
unsignedShort
unsignedShort

Reputation: 91

How to determine disk I/O requirement for a particular sorting algorithm given cluster size and output buffer

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?

Upvotes: 8

Views: 906

Answers (1)

Fraser
Fraser

Reputation: 17094

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.

Upvotes: 1

Related Questions