Question

Consider an array \(A = [10,\ 7,\ 8,\ 19,\ 41,\ 35,\ 25,\ 31]\). Suppose the merge sort algorithm is executed on array \(A\) to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations.

A merge operation on sorted left array \(L\) and sorted right array \(R\) is said to be void if the output of the merge operation is the elements of array \(L\) followed by the elements of array \(R\).

The number of void merge operations among these 7 merge operations is ______.

Hint:

A merge is void exactly when every element of the left half is already smaller than every element of the right half, so compare the largest value on the left with the smallest value on the right.

Answer 1

Correct Answer: 3

Step 1: Understand what a void merge means.
Merge sort splits the array in half again and again until single element pieces are left, then merges pairs back together in sorted order. A merge of a left part \(L\) and a right part \(R\) is called void when the sorted output turns out to be exactly \(L\) written first and then \(R\) written after it. This happens only when every value in \(L\) is already less than or equal to every value in \(R\), so the merge step needs no real interleaving.

Step 2: Split the array the way merge sort does.
The array is
\[ A = [10,\ 7,\ 8,\ 19,\ 41,\ 35,\ 25,\ 31] \]
Merge sort splits this into two halves:
\[ L_1 = [10,\ 7,\ 8,\ 19] \quad \text{and} \quad R_1 = [41,\ 35,\ 25,\ 31] \]
Each half is split again into single elements:
\[ [10],[7] \ \ \ [8],[19] \ \ \ [41],[35] \ \ \ [25],[31] \]
This gives 4 pairs at the bottom, so 4 merges happen first.

Step 3: Perform the 4 bottom level merges.
Merge 1: \(L=[10]\), \(R=[7]\). The sorted output is \([7,10]\). Writing \(L\) then \(R\) would give \([10,7]\), which does not match, so this merge is not void.
Merge 2: \(L=[8]\), \(R=[19]\). The sorted output is \([8,19]\). Since \(8\) is already smaller than \(19\), writing \(L\) then \(R\) already gives \([8,19]\), matching the output. This merge is void.
Merge 3: \(L=[41]\), \(R=[35]\). The sorted output is \([35,41]\). Writing \(L\) then \(R\) would give \([41,35]\), which does not match, so this merge is not void.
Merge 4: \(L=[25]\), \(R=[31]\). The sorted output is \([25,31]\). Since \(25\) is already smaller than \(31\), writing \(L\) then \(R\) matches the output. This merge is void.

Step 4: Perform the 2 second level merges.
Merge 5 combines \([7,10]\) and \([8,19]\). Comparing one by one: \(7\) is smaller than \(8\), so take \(7\) first; then \(8\) is smaller than \(10\), so take \(8\) next; then \(10\) is smaller than \(19\), so take \(10\); finally take the remaining \(19\). The sorted output is \([7,8,10,19]\). Writing \(L\) then \(R\) would give \([7,10,8,19]\), which does not match, so this merge is not void.
Merge 6 combines \([35,41]\) and \([25,31]\). The sorted output is \([25,31,35,41]\). Writing \(L\) then \(R\) would give \([35,41,25,31]\), which does not match, so this merge is not void.

Step 5: Perform the final top level merge.
Merge 7 combines \([7,8,10,19]\) and \([25,31,35,41]\). The largest value in the left part is \(19\) and the smallest value in the right part is \(25\), so every left value is already smaller than every right value. The sorted output is simply the left part followed by the right part, \([7,8,10,19,25,31,35,41]\). This merge is void.

Step 6: Count the void merges.
The void merges happened at Merge 2, Merge 4, and Merge 7. That is 3 void merges out of the 7 total merges.

Step 7: Final answer.
\[ \boxed{3} \]