In the external version of mergesort,if we begin by performing 16 sorted runs with 1 block each,what is the next step?
A)1 sorted run,16 blocks each
B)2 sorted runs,8 blocks each
C)4 sorted runs,4 blocks each
D)8 sorted runs,2 blocks each

Question

Quizplus · Accepted Answer

In the next step, we need to merge the 16 sorted runs into 8 sorted runs with 2 blocks each. This is because in mergesort, we always merge two sorted lists at a time, and we need to continue this process until we have a single sorted list. Therefore, we need to continue dividing the runs into smaller sorted lists until we have runs with only two blocks each.

In the External Version of Mergesort,if We Begin by Performing