Suppose you have a file with
1
0
0
0
0
0
pages to be sorted with general external merge sort
(
without tournament sort and without blocked disk access improvements
)
.
Assume that you have
2
0
0
buffer pages available in memory that can be used for sorting. Answer the
following questions:
a
)
How many sorted runs will the general external merge sort produce at the end of the first pass?
b
)
How many passes will it take to sort the file completely? c
)
What is the total I
/
O cost
(
the number of disk access made
)
of sorting the file
?

Question

Suppose you have a file with 
1
0
0
0
0
0
 ﻿pages to be sorted with general external merge sort 
(
without tournament sort and without blocked disk access improvements
)
.
 ﻿Assume that you have 
2
0
0
 ﻿buffer pages available in memory that can be used for sorting. Answer the
following questions:
a
)
 ﻿How many sorted runs will the general external merge sort produce at the end of the first pass?
b
)
 ﻿How many passes will it take to sort the file completely? c
)
What is the total I
/
O cost 
(
 ﻿the number of disk access made
)
 ﻿of sorting the file 
?

Accepted Answer

∻Answer to part a)∻ ‖ ▪ ⋮ Given file size: 1,000,000 pages ‖ ‖ ▪ ⋮ Buffer size: 200 pages ‖ ‖ ▪ ⋮ Number of runs: Total pages / Buffer size ‖ ‖ ▪ ⋮ Calculation: 1,000,000 / 200 = 5000 runs ‖ ‖ ▪ ⋮ Conclusion: The general external merge sort will produce 5000 sorted runs at the end of the first pass ‖ ⚹ At the end of the first pass, the general external merge sort will produce 5000 sorted runs. ⚹ ∻Answer to part b)∻ ‖ ▪ ⋮ Number of runs after the first pass: 5000 ‖ ‖ ▪ ⋮ Buffer size: 200 pages (199 for input, 1 for output) ‖ ‖ ▪ ⋮ Number of runs that can be merged in each pass: 199 ‖ ‖ ▪ ⋮ Calculation of passes: ceil(log_199(5000)) ‖ ‖ ▪ ⋮ Using logarithm to calculate the number of passes needed ‖ ‖ ▪ ⋮ Conclusion: It will take 4 passes to completely sort the file ‖ ⚹ It will take 4 passes to completely sort the file. ⚹ ∻Answer to part c)∻ ‖ ▪ ⋮ Number of runs: 5000 ‖ ‖ ▪ ⋮ Number of passes: 4 ‖ ‖ ▪ ⋮ I/O cost per pass: 2 * Total pages (read + write) ‖ ‖ ▪ ⋮ Total I/O cost: Number of passes * I/O cost per pass ‖ ‖ ▪ ⋮ Calculation: 4 * 2 * 1,000,000 = 8,000,000 disk accesses ‖ ‖ ▪ ⋮ Conclusion: The total I/O cost of sorting the file is 8,000,000 disk accesses ‖ ⚹ The total I/O cost of sorting the file is 8,000,000 disk accesses. ⚹

Sia