in Algorithms retagged by
6,624 views
2 votes
2 votes
Assume 5 buffer pages are available to sort a file of 105 pages. The cost of sorting using m-way merge sort is
A.    206
B.    618
C.    840
D.    926
in Algorithms retagged by
by
6.6k views

1 Answer

1 vote
1 vote
In the first pass we can create [105/5]=21 sorted sub-files,each 5 pages long.
In the second pass by 4-way merging (4 because one of the 5 available buffers has to be reserved for holding the output),

 We can create [21/4]=6 sorted sub-files,each 20 pages long (except the last).

Again applying 4-way merge sort,we get create [6/4]=2 sorted sub-files. These two can be merged to get the final sorted file. We need a total of 4 passes. Total cost will be 2 x 105 x 4=840 units.

Hence obtion C.

4 Comments

can u share the link for m-way merge sort.

 

thanku
0
0
Why 2*105*4???  why not 105*4???
0
0
What is here 2 and 4 in multiplication to get result?
0
0
Answer:

Related questions