Question

Given the list { 9, 8, 7, 6, 5, 4, 3, 2, 1 }, if mergesort is used to sort the list in ascending order, how many times will the subroutine merge get called before termination? a.6 b.7 c.8 d.9

Answer 1

The subroutine merge will be called 7 times before termination.

Step-by-step explanation:

Mergesort is a divide-and-conquer algorithm that splits an array into two halves, recursively sorts each half, and then merges the two sorted halves back together to form a sorted array.

In this case, the original list has 9 elements, so the algorithm will start by splitting it into two halves: {9, 8, 7, 6} and {5, 4, 3, 2, 1}.

The algorithm will then recursively sort each half, resulting in the following splits:

1. {9, 8, 7, 6} -> {9, 8} -> {9}, {8} -> merge
2. {5, 4, 3, 2, 1} -> {5, 4}, {3, 2, 1} -> {5}, {4} -> merge
3. {3, 2, 1} -> {3}, {2, 1} -> {2}, {1} -> merge

Finally, the algorithm will merge the sorted halves back together to get the final sorted list:

1. {9}, {8} -> merge
2. {5}, {4} -> merge
3. {3}, {2} -> merge
4. {2}, {1} -> merge
5. {3, 2}, {1} -> merge
6. {5, 4}, {3, 2, 1} -> merge
7. {9, 8}, {5, 4, 3, 2, 1} -> merge

Therefore, the subroutine merge will be called 7 times before the termination.