Question

Assuming that a query has a buffer holding up to 3 blocks, and each block can hold two records. Use merge-sort to sort the following records in ascending order: 10, 11, 1, 5, 90, 1, 2, 101
How many runs will be produced in the whole algorithm and what are the contents of the runs?

Answer 1

Answer:

a) 5 runs will be generated.

b) Since the buffer can hold 3 records, the first 3 runs are (1, 10, 11), (1, 5, 90) and (2, 10). Then we need to reserve one block as output buffer, the algorithm can merge two runs at most at the same time. As a result, we can choose to merge the first two runs into a larger one: (1,1,5,10,11,90), which is merged with the run (2, 10) to generate the final output.

Explanation:

5 runs will be generated.

Since the buffer can hold 3 records, the first 3 runs are (1, 10, 11), (1, 5, 90) and (2, 10). Then we need to reserve one block as output buffer, the algorithm can merge two runs at most at the same time. As a result, we can choose to merge the first two runs into a larger one: (1,1,5,10,11,90), which is merged with the run (2, 10) to generate the final output.