GATE 2026 CS (CS2) – Question 32
Consider an array $A=[10,7,8,19,41,35,25,31]$. Suppose merge sort is executed on $A$ to sort it in increasing order. The 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 $L$ followed by the elements of $R$. The number of void merge operations among these 7 merge operations is __________. (answer in integer)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 3
Explanation
The level-1 merges are $(10,7)$, $(8,19)$, $(41,35)$, and $(25,31)$. Among these, $(8,19)$ and $(25,31)$ are void because the left element is already no larger than the right element; the other two are not void. At level 2, the merges $[7,10]+[8,19]$ and $[35,41]+[25,31]$ are both not void. At level 3, the final merge $[7,8,10,19]+[25,31,35,41]$ is void because every element in the left half is smaller than every element in the right half. Hence the total number of void merges is $2+1=3$.