Insertion sort looks simple, yet exams test pass counting, loop conditions, shifts, complexity, and suitable inputs. Commit to an answer before checking the explanation. If the idea slips, revise Sorting Algorithms: Complexity and Comparison, then use Data Structures MCQs for neighbouring topics.
How insertion sort actually works
Insertion sort grows a sorted prefix. It shifts larger values right, then places the next key in the gap.
Q1. Which of the following best describes the working of Insertion Sort? (BELTRON Programmer 2025)
(a) Swap adjacent elements until sorted
(b) Select minimum repeatedly
(c) Move through the array and insert elements in the correct position in a growing sorted list
(d) Divide and conquer
Answer: (c). The sorted part grows by one element per pass as each key enters its correct position. Option (a) describes bubble sort, (b) selection sort, and (d) the strategy used by merge sort and quicksort. It is like arranging playing cards in your hand (see the solved page).
Q2. Consider the code that runs insertion sort:
for (i = 1; i < array_size; i++){ value = arr[i]; j = i; while (________){ arr[j] = arr[j-1]; j = j-1; } arr[j] = value; }
Which condition correctly implements the while loop? (CoCubes 2024)
(a) (j > 0) || (arr[j - 1] > value)
(b) (j > 0) && (arr[j - 1] > value)
(c) (j > 0) && (arr[j + 1] > value)
(d) (j > 0) && (arr[j + 1] < value)
Answer: (b). Shift only while j > 0 and the left neighbour is greater than the key. The && short-circuits safely at the boundary. Options (c) and (d) inspect the wrong side, while || can evaluate arr[j - 1] when j is zero (see the solved page).
Tracing the insertion sort passes
Pass 1 inserts the element at index 1. After pass k, the first k + 1 elements are sorted. Leave the unvisited tail untouched.
Q3. Consider an array of length 5, arr[5] = {9, 7, 4, 2, 1}. What are the steps of insertions done while running insertion sort on the array? (AMCAT 2024)
(a) 7 9 4 2 1 | 4 7 9 2 1 | 2 4 7 9 1 | 1 2 4 7 9
(b) 9 7 4 1 2 | 9 7 1 2 | 9 1 2 4 7 | 1 2 4 7 9
(c) 7 4 2 1 9 | 4 2 1 9 7 | 2 1 9 7 4 | 1 9 7 4 2
(d) 7 9 4 2 1 | 2 4 7 9 1 | 4 7 9 2 1 | 1 2 4 7 9
Answer: (a). Insert 7 before 9: 7 9 4 2 1. Insert 4: 4 7 9 2 1. Key 2 moves to the front: 2 4 7 9 1. Key 1 then gives 1 2 4 7 9. Option (d) scrambles the middle passes (see the solved page).
Q4. For the array 34, 8, 64, 51, 32, 21, how will the array look after the second pass of Insertion Sort? (TCS 2024)
(a) 8, 21, 32, 34, 51, 64
(b) 8, 32, 34, 51, 64, 21
(c) 8, 34, 51, 64, 32, 21
(d) 8, 34, 64, 51, 32, 21
Answer: (d). Pass 1 inserts 8 before 34, giving 8, 34, 64, 51, 32, 21. In pass 2, key 64 is already greater than 34, so the array does not change (see the solved page).
Q5. If the array A contains the items 10, 4, 7, 23, 67, 12 and 5 in that order, what will be the resultant array A after the third pass of insertion sort? (ISRO 2020)
(a) 67, 12, 10, 5, 4, 7, 23
(b) 4, 7, 10, 23, 67, 12, 5
(c) 4, 5, 7, 67, 10, 12, 23
(d) 10, 7, 4, 67, 23, 12, 5
Answer: (b). Pass 1 gives 4, 10, 7, 23, 67, 12, 5. Pass 2 inserts 7 between 4 and 10, giving 4, 7, 10, 23, 67, 12, 5. In pass 3, key 23 is already greater than 10, so it stays where it is. The unvisited tail remains unchanged (see the solved page).
Best case, worst case and pre-sorted input
Existing order reduces insertion sort's work. Reverse order maximises it.
Q6. What is the worst-case time complexity of insertion sort? (TPSC 2026, Computer Science)
(a) O(n)
(b) O(n log n)
(c) O(n^2)
(d) O(log n)
Answer: (c). A reverse-sorted array is the worst case. The successive keys require 1, 2, ..., n - 1 shifts, for a total of n(n - 1)/2. The quadratic term dominates, so the complexity is O(n^2) (see the solved page).
Q7. What is the running time of an insertion sort algorithm if the input is pre-sorted? (IBM 2024)
(a) O(N^2)
(b) O(N log N)
(c) O(N)
(d) O(M log N)
Answer: (c). For each of the N - 1 keys, the first comparison with the left neighbour fails because the neighbour is not greater. There are no shifts. The work grows linearly, so the best-case running time is O(N) (see the solved page).
Q8. Which of the following sorting algorithms has the lowest time complexity in the best-case scenario among these standard implementations, assuming Bubble Sort performs all passes without an early-exit check? (TPSC 2024, Assistant CEO)
(a) Selection sort
(b) Merge Sort
(c) Insertion sort
(d) Bubble sort
Answer: (c). On sorted input, insertion sort performs one failed inner-loop test per key and runs in O(n). Selection sort stays O(n^2) and merge sort O(n log n). The basic bubble-sort version assumed here also stays quadratic (see the solved page).
When insertion sort is the right choice
Insertion sort works in place and has low overhead on small or nearly sorted inputs.
Q9. In which case is Insertion Sort better than Quick Sort and Merge Sort? (IBPS 2025 Mains)
(a) Large, random input
(b) Large input, needs stable sort
(c) Small, nearly sorted, uses less memory
(d) Sorting linked lists
(e) Parallel sorting of big data
Answer: (c). A small, nearly sorted array needs few shifts, while insertion sort avoids recursion and auxiliary arrays. Its low overhead also makes it useful for small subarrays inside hybrid sorts (see the solved page).
Q10. Consider the array 23, 32, 45, 69, 72, 73, 89, 97. Which algorithm uses the least number of comparisons among the array elements to sort it in ascending order? (TPSC 2025, Senior Informatics Officer)
(a) Selection sort
(b) Merge sort
(c) Insertion sort
(d) Quicksort using the last element as pivot
Answer: (c). The values are already sorted. Insertion sort tests each of the seven keys once against its left neighbour, needing seven comparisons and no shifts. Selection sort scans every suffix, merge sort still merges, and last-pivot quicksort repeatedly partitions the array (see the solved page).
The two GATE twists: binary search and inversions
Binary search can reduce comparisons, but insertion still moves elements. The inversion count measures those shifts.
Q11. The usual Theta(n^2) implementation of Insertion Sort uses linear search to find where an element goes in the sorted part. If instead we use binary search to find the position, the worst-case running time will (GATE 2003)
(a) remain Theta(n^2)
(b) become Theta(n (log n)^2)
(c) become Theta(n log n)
(d) become Theta(n)
Answer: (a). Binary search finds the ith key's position in Theta(log i) comparisons, making total comparisons Theta(n log n). Opening the gap can still require i shifts. Their total is 1 + 2 + ... + (n - 1) = n(n - 1)/2, so Theta(n^2) dominates (see the solved page).
Q12. In a permutation a1...an of n distinct integers, an inversion is a pair (ai, aj) with i < j and ai > aj. What is the worst-case time complexity of Insertion Sort if the inputs are restricted to permutations of 1...n with at most n inversions? (GATE 2003)
(a) Theta(n^2)
(b) Theta(n log n)
(c) Theta(n^1.5)
(d) Theta(n)
Answer: (d). Every shift moves the key across one larger earlier element, removing exactly one inversion. With I inversions, insertion sort takes Theta(n + I): Theta(n) for the outer pass plus work proportional to the shifts. Since I is at most n, this becomes Theta(n + n) = Theta(n) (see the solved page).
How insertion sort is examined, and what to do next
The recurring tests are traces, complexity, suitable inputs, and comparisons versus shifts. After pass k, the first k + 1 elements are sorted.
If a question exposed a gap, rebuild it through GATE CS Exam, then practise previous-year sorting sets in GATE Guidance by Sanchit Sir. Placement aspirants can continue with Coding for Placements.
Solve, review only what you missed, then attempt the set again after a week.
