IAE Academy

GATE 2026 CS2 Q.32: solution and answer

GATE 2026 · CS2Q.32 · 1 mark · NAT

Consider an array . Suppose the merge sort algorithm is executed on array 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 and sorted right array is said to be void if the output of the merge operation is the elements of array followed by the elements of array .

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

See the question in the paper
GATE 2026 CS2 question 32Tap to open full size

Answer and solution

ANSWER

The number of void merge operations is 3.

Official answer: 3Source: Official answer key, GATE 2026 CS2 (IIT Guwahati)

  1. Merge sort recursively halves A=[10,7,8,19,41,35,25,31] down to 8 singleton leaves in original order: [10],[7],[8],[19],[41],[35],[25],[31], then merges back up in 3 levels totaling 4+2+1=7 merges, matching the stem.

  2. Level 1 merges (adjacent singleton pairs): merge([10],[7])→[7,10], but L followed by R=[10,7]≠[7,10] → NOT void. merge([8],[19])→[8,19]=L+R=[8,19] → VOID. merge([41],[35])→[35,41], L+R=[41,35]≠ → NOT void. merge([25],[31])→[25,31]=L+R → VOID.

  3. Level 2 merges: merge([7,10],[8,19])→[7,8,10,19], L+R=[7,10,8,19]≠ → NOT void. merge([35,41],[25,31])→[25,31,35,41], L+R=[35,41,25,31]≠ → NOT void.

  4. Final merge (level 3): merge([7,8,10,19],[25,31,35,41]) — since max(L)=19<min(R)=25, the merged sorted output equals L followed by R exactly → VOID.

  5. Total void merges = 2 (level 1) + 0 (level 2) + 1 (final) = 3.

KEY IDEA

In standard top-down merge sort, the array is recursively halved until singletons, then merged back up level by level. A merge of and is "void" exactly when every element of is already every element of — i.e. — so the merged output equals followed by unchanged.

WATCH OUT FOR

Assuming a merge is void whenever and are each individually already sorted (true for every leaf-pair merge by definition) rather than checking whether 's elements are ALL less than 's elements; e.g. merge([10],[7]) has two "sorted" singletons but is NOT void since 10 > 7, so the output [7,10] differs from L followed by R = [10,7].

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 18 Sorting & hashing questions, with notes

More Sorting & hashing questions