High yield ●●●

🔀 Sorting & Searching

Why it matters: Complexities, stability, number of swaps and comparisons, and quicksort partitioning appear in almost every paper.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 6 done.

Formulas

Comparisons
bubble/selection n(n − 1)/2; insertion: n − 1 (best) to n(n − 1)/2; merge ≈ n log₂ n − n + 1 (worst)
Inversions
insertion-sort shifts = number of inversions; reversed array has n(n − 1)/2
Quick sort
average / best 2T(n/2) + n → Θ(n log n); worst T(n − 1) + n → Θ(n²)
Lower bound
decision tree height ≥ ⌈log₂ n!⌉ = Ω(n log n)
Binary search
worst case ⌊log₂ n⌋ + 1 comparisons; min and max together: ⌈3n/2⌉ − 2
Counting sort / radix
Θ(n + k); radix Θ(d(n + k))

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Worst / best / average case time of a sort
Which sort is Θ(n²) on sorted input; which is Θ(n log n) always.
★★★
Number of swaps or comparisons on a given input
Run insertion, bubble or selection sort by hand, or count inversions.
★★★
Quick sort partition / recurrence
Array after one partition, or the recurrence when the split is 1 : 9 or n/10 : 9n/10.
★★★
Stable / in-place / space properties
Pick the algorithm that satisfies a property.
★★★
Binary search and min-max problems
Number of probes, or minimum comparisons to find min and max.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

9 real questions from the official GATE CSE papers (2014 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

9 questions · 0 correct of 0 attempted · marks 0 / 12

Year:
GATE 2025 CS1 · Q33NAT1 mark
The pseudocode of a function fun() is given below:
fun(int A[0..n−1]) {
  for i = 0 to n − 2: for j = 0 to n − i − 2: if (A[j] > A[j + 1]) then swap A[j] and A[j + 1]
}
Let A[0..29] be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun() is called with A[0..29] as argument, is ______.
GATE 2025 CS2 · Q41MCQ2 marks
An array A of length n with distinct elements is said to be bitonic if there is an index 1 ≤ i ≤ n such that A[1..i] is sorted in the non-decreasing order and A[i + 1..n] is sorted in the non-increasing order. Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array A?
GATE 2021 Set 1 · Q2MCQ1 mark
Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?
GATE 2021 Set 1 · Q9MCQ1 mark
Consider the following array: 23 32 45 69 72 73 89 97. Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?
GATE 2019 Set 2 · Q20NAT1 mark
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is ______.
GATE 2019 Set 2 · Q37MCQ2 marks
There are n unsorted arrays: A1, A2, …, An. Assume that n is odd. Each of A1, A2, …, An contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A1, A2, …, An is
GATE 2016 Set 1 · Q13MCQ1 mark
The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
GATE 2014 Set 1 · Q14MCQ1 mark
Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
GATE 2014 Set 1 · Q39NAT2 marks
The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is ______.

Common traps

Quick sort is Θ(n²) on already sorted input when the pivot is first or last.
Merge sort needs O(n) extra space; heap sort needs none; both are Θ(n log n).
Selection sort does few swaps but not few comparisons.
The Ω(n log n) bound applies only to comparison sorts: counting sort beats it.