GATE CS 2026 Set 2 Q22 — Searching, Sorting, Hashing

A merge operation on sorted arrays $L$ and $R$ is void if the merged output is exactly $L$ concatenated with $R$. Since $L$ and $R$ are already sorted, this condition holds if and only if:

Let us trace the standard merge sort execution on the array $A = [10, 7, 8, 19, 41, 35, 25, 31]$ by recursively splitting it into halves:

1. Merge 1: $L = [10]$, $R = [7]$
   $\max(L) = 10 > \min(R) = 7$ → Not Void
2. Merge 2: $L = [8]$, $R = [19]$
   $\max(L) = 8 \le \min(R) = 19$ → Void
3. Merge 3: $L = [7, 10]$, $R = [8, 19]$
   $\max(L) = 10 > \min(R) = 8$ → Not Void
4. Merge 4: $L = [41]$, $R = [35]$
   $\max(L) = 41 > \min(R) = 35$ → Not Void
5. Merge 5: $L = [25]$, $R = [31]$
   $\max(L) = 25 \le \min(R) = 31$ → Void
6. Merge 6: $L = [35, 41]$, $R = [25, 31]$
   $\max(L) = 41 > \min(R) = 25$ → Not Void
7. Merge 7: $L = [7, 8, 10, 19]$, $R = [25, 31, 35, 41]$
   $\max(L) = 19 \le \min(R) = 25$ → Void

Thus, there are exactly 3 void merge operations (Merge 2, Merge 5, and Merge 7).