GATE CS Mastery
Cheat sheets

GATE CS 2026 Set 2 · Algorithms

Question 32

NAT1 markNo negative markingEasy (estimate)

Question

Consider an array A=[10,7,8,19,41,35,25,31]A = [10, 7, 8, 19, 41, 35, 25, 31]. Suppose the merge sort algorithm is executed on array AA 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 LL and sorted right array RR is said to be void if the output of the merge operation is the elements of array LL followed by the elements of array RR.

The number of void merge operations among these 7 merge operations is __________. (answer in integer)

Official answer and solution
Official answer
3
From
Official GATE 2026 answer key

Solution

Check each of the 7 merge steps in bottom-up/top-down merge sort to see when max⁡(L)≤min⁡(R)\max(L) \le \min(R).

A merge of sorted arrays LL and RR (with distinct elements) produces LL followed by RR if and only if every element of LL is smaller than every element of RR, i.e., max⁡(L)<min⁡(R)\max(L) < \min(R).

Tracing the 7 merges on A=[10,7,8,19,41,35,25,31]A = [10, 7, 8, 19, 41, 35, 25, 31]:

  1. Level 1 (size 1 + 1):
    • Merge [10][10] and [7]→[7,10][7] \rightarrow [7, 10] (not void, 10>710 > 7).
    • Merge [8][8] and [19]→[8,19][19] \rightarrow [8, 19] (void, 8<198 < 19).
    • Merge [41][41] and [35]→[35,41][35] \rightarrow [35, 41] (not void, 41>3541 > 35).
    • Merge [25][25] and [31]→[25,31][31] \rightarrow [25, 31] (void, 25<3125 < 31).
  2. Level 2 (size 2 + 2):
    • Merge L=[7,10]L = [7, 10] and R=[8,19]→[7,8,10,19]R = [8, 19] \rightarrow [7, 8, 10, 19] (not void, 10>810 > 8).
    • Merge L=[35,41]L = [35, 41] and R=[25,31]→[25,31,35,41]R = [25, 31] \rightarrow [25, 31, 35, 41] (not void, 41>2541 > 25).
  3. Level 3 (size 4 + 4):
    • Merge L=[7,8,10,19]L = [7, 8, 10, 19] and R=[25,31,35,41]→[7,8,10,19,25,31,35,41]R = [25, 31, 35, 41] \rightarrow [7, 8, 10, 19, 25, 31, 35, 41] (void, since max⁡(L)=19<min⁡(R)=25\max(L) = 19 < \min(R) = 25).

Total void merge operations =2+0+1=3= 2 + 0 + 1 = 3.

Final answer

3

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question
32 of 65
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.