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: Turn the definition into a simple test.
A merge of $L$ and $R$ is void exactly when the final sorted list equals $L$ followed by $R$. That can only happen if every element of $L$ is already less than or equal to every element of $R$, because then the merge algorithm never needs to pick an element from $R$ before finishing $L$. So the quick test is: a merge is void exactly when the largest value in $L$ is no bigger than the smallest value in $R$.

Step 2: Build the merge tree for the array.
The array is $A=[10,7,8,19,41,35,25,31]$. Merge sort breaks it down as: $[10,7,8,19]$ and $[41,35,25,31]$, which further break into $[10],[7]$, $[8],[19]$, $[41],[35]$, $[25],[31]$. This gives 7 merges in total: 4 at the leaf level, 2 at the middle level, and 1 at the top.

Step 3: Apply the max-min test to the 4 leaf merges.
$L=[10], R=[7]$: the largest value in $L$ is $10$ and the smallest in $R$ is $7$. Since $10$ is bigger than $7$, this merge is not void.
$L=[8], R=[19]$: the largest in $L$ is $8$ and the smallest in $R$ is $19$. Since $8$ is not bigger than $19$, this merge is void.
$L=[41], R=[35]$: the largest in $L$ is $41$ and the smallest in $R$ is $35$. Since $41$ is bigger than $35$, this merge is not void.
$L=[25], R=[31]$: the largest in $L$ is $25$ and the smallest in $R$ is $31$. Since $25$ is not bigger than $31$, this merge is void.

Step 4: Work out the sorted results these leaf merges give.
Sorting $[10],[7]$ gives $[7,10]$. Sorting $[8],[19]$ gives $[8,19]$. Sorting $[41],[35]$ gives $[35,41]$. Sorting $[25],[31]$ gives $[25,31]$. These four results become the inputs to the middle level.

Step 5: Apply the test to the 2 middle merges.
$L=[7,10], R=[8,19]$: the largest in $L$ is $10$ and the smallest in $R$ is $8$. Since $10$ is bigger than $8$, this merge is not void.
$L=[35,41], R=[25,31]$: the largest in $L$ is $41$ and the smallest in $R$ is $25$. Since $41$ is bigger than $25$, this merge is not void.
These two merges produce $[7,8,10,19]$ and $[25,31,35,41]$.

Step 6: Apply the test to the final top merge.
$L=[7,8,10,19], R=[25,31,35,41]$: the largest in $L$ is $19$ and the smallest in $R$ is $25$. Since $19$ is not bigger than $25$, this merge is void.

Step 7: Add up the void merges.
Void merges happened at the leaf merge of $[8],[19]$, the leaf merge of $[25],[31]$, and the final top merge. That is 3 void merges out of 7 total.
$$ \boxed{3} $$