Question

Computer Science

Posted 2 months ago

```
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
?
```

Sign in to unlock the answer

Answer from Sia

Posted 2 months ago

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.

Not the question you are looking for? Ask here!

Enter question by text

Enter question by image

Upgrade to Asksia Pro

Join a AskSia's Pro Plan, and get 24/7 AI tutoring for your reviews, assignments, quizzes and exam preps.

Unlimited chat query usages

Strong algorithms that better know you

Early access to new release features

Study Other Question