The GATE Grind

GATE 2025 DA – Question 29

Programming, Data Structures and Algorithms · Searching and sorting algorithms · 1 mark · Multiple select

Suppose that insertion sort is applied to the array [1, 3, 5, 7, 9, 11, $x$, 15, 13] and it takes exactly two swaps to sort the array. Select all possible values of $x$.

  1. 10
  2. 12
  3. 14
  4. 16

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) 10; (C) 14

Explanation

The number of swaps insertion sort makes is the number of inversions (pairs in the wrong order). The pair 15, 13 is already one inversion, so $x$ must create exactly one more. For $x = 10$ the only larger element before it is 11, which gives 1 inversion and a total of 2. For $x = 12$ there is no inversion at all (1 swap in total). For $x = 14$ the only smaller element after it is 13, which gives 1 more inversion (14 is before 15, which is fine) and a total of 2. For $x = 16$, both 15 and 13 are after it and smaller, which gives 2 more and a total of 3. So $x$ can be 10 or 14.