Problem 4: External Sorting Answer the following questions for each of these sce
ID: 3713883 • Letter: P
Question
Problem 4: External Sorting Answer the following questions for each of these scenarios, assuming that our most general external sorting algorithm is used:
A. A file with 100,000 pages and 30 available buffer pages.
B. A file with 200,000 pages and 50 available buffer pages.
C. A file with 20,000,000 pages and 170 available buffer pages.
Questions: 1. How many runs will you produce in the first pass?
2. How many passes will it take to sort the file completely?
3.What is the total I/O cost of sorting the file?
4. How many buffer pages do you need to sort the file completely in just two passes?
Explanation / Answer
Answer)
1. In first pass, sorted runs are: (N/B), N-number of file pages, B - number of available buffer pages
a) (100000/30) = 3334 sorted runs
b) (200000/50) = 4000 sorted runs
c) (20000000/170) = 117648 sorted runs
2.
Formula is = logB?1 [N/B]) + 1
The number of passes will it take to sort the file completely are:
a) (log2 3334) + 1 = 13 passes
b) (log4 4000) + 1 = 7 passes
c) (log16 117648) + 1 = 6 passes
3. Total I/O cost of sorting the file using formula 2*N*(number of passes) are:
a) 2*100000*13 = 2600000
b) 2*200000*7 = 2800000
c) 2*20000000*6 = 240000000