Skip to content
GATEiit

GATE CSE 2026 Session 2 Q32: Number of 'void' merges in merge sort of an 8-element array

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)

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 3 (official GATE 2026 final answer key)

Concept used: A merge is void exactly when the largest element of LL is smaller than the smallest element of RR.

First step: Write out the merge tree: four merges of pairs, two of 4-element halves, and the final merge; test each.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 2 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2026 Session 2 questions →