GATE CS · DA

Searching, sorting and hashing

Searching, sorting and hashing cover how to find, order and index data. The topic includes linear and binary search (with exact comparison counts) and the elementary sorts (bubble, selection, insertion). It then covers the efficient comparison sorts (merge, quick, heap), which cannot beat the Omega(n log n) lower bound, and the non-comparison sorts (counting, radix), which beat it when keys are small integers. Finally it covers hash tables (chaining, linear and quadratic probing, double hashing) with their load-factor-dependent probe counts. Most questions come down to tracing an algorithm by hand under a stated convention, or plugging values into one of a small set of standard results. Both are drilled here.

18 previous-year questions · 18 solved · 5 practice questions

1. Linear search and binary search

Searching means locating a key in a collection of $n$ elements. Linear search scans one element at a time and needs no ordering. Binary search repeatedly halves the search space. It requires the array to be sorted and O(1) random access to any index. Applied to an unsorted array it can miss a key that is present, and on a linked list reaching the middle alone costs $O (n)$ .

Linear search procedure

Start at index 0.
Compare the current element with the key.
If equal, return the index (success).
Otherwise move to the next index.
If the end of the array is reached with no match, report failure.

LINEAR SEARCH: NUMBER OF KEY COMPARISONS

C_{unsuccessful} (n) = n, C_{successful, avg} (n) = \frac{1 + 2 + \dots + n}{n} = \frac{n + 1}{2}

The successful-search average assumes the key is present and equally likely to be at each of the $n$ positions. Both the worst case and the average case are $O (n)$ .

Binary search procedure (array sorted ascending, 0-indexed, `low = 0`, `high = n - 1`)

While low <= high, compute mid = low + (high - low) / 2 (integer division). This equals (low + high) / 2 whenever that sum does not overflow int; the first form simply avoids the overflow for very large indices.
If a[mid] == key, return mid.
If a[mid] < key, set low = mid + 1 (search the right half).
If a[mid] > key, set high = mid - 1 (search the left half).
If the loop ends with low > high, report failure.

BINARY SEARCH COMPLEXITY

T (n) = T (\frac{n}{2}) + O (1) \Rightarrow T (n) = O (lo g n), C_{worst} (n) = ⌊ lo g_{2} n ⌋ + 1

Convention: each probe of a[mid] counts as one (three-way) comparison. The worst case $⌊ lo g_{2} n ⌋ + 1$ holds for both successful and unsuccessful search. If a question counts the == test and the < test as separate comparisons, recount under its rule. Valid only for a sorted array with random access.

WORKED EXAMPLE · TRACE

Array (sorted, 0-indexed): [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91], so $n = 11$ . Using the procedure above, how many probes does binary search make to find key = 72? Which key needs the worst-case number of probes, and how many is that?

Solution

Key 72. Probe 1: low = 0, high = 10, mid = 5, a[5] = 23 < 72, so low = 6.
Probe 2: low = 6, high = 10, mid = 6 + 4/2 = 8, a[8] = 56 < 72, so low = 9.
Probe 3: low = 9, high = 10, mid = 9 + 1/2 = 9, a[9] = 72: found at index 9 after 3 probes.
Key 91 follows the same path to low = 9. Probe 3 gives a[9] = 72 < 91, so low = 10. Probe 4: mid = 10, a[10] = 91, found. That is 4 probes.
Check: $⌊ lo g_{2} 11 ⌋ + 1 = 3 + 1 = 4$ , so no key (and no unsuccessful search) needs more than 4 probes.

Answer: Key 72 is found at index 9 in 3 probes. Key 91 needs the worst case of 4 probes, which matches $⌊ lo g_{2} 11 ⌋ + 1 = 4$ .

FINDING THE MINIMUM AND MAXIMUM TOGETHER

C_{m i n and m a x} (n) = ⌈ \frac{3 n}{2} ⌉ - 2 (n \geq 2)

Method: take the elements in pairs. Compare the two elements of each pair with each other, then the smaller with the current minimum and the larger with the current maximum. That is 3 comparisons per pair instead of 4. Finding only the maximum (or only the minimum) takes exactly $n - 1$ comparisons. Both counts are the best possible for comparison-based algorithms.

EXAM TIP

When a question asks for the worst-case number of comparisons for a specific $n$ (e.g. $n = 100$ gives $⌊ lo g_{2} 100 ⌋ + 1 = 6 + 1 = 7$ ), use $⌊ lo g_{2} n ⌋ + 1$ directly, after checking how the question counts a comparison. Also check that the array is actually sorted before applying binary search.

2. Sorting fundamentals: stability, in-place, and the comparison lower bound

Convention for this whole topic unless a question says otherwise: complexities are worst case, logarithms are base 2, and programs are C with 0-indexed arrays and 4-byte int. A sort is stable if two elements with equal keys keep their original relative order in the output. A sort is in-place if it uses only $O (1)$ extra storage outside the input array. The recursion stack is reported separately, which is why quicksort is called in-place even though its stack uses $O (lo g n)$ space on average. If a question gives its own definition of in-place, use that.

Core vocabulary

Term	Meaning	Why it matters
Comparisons	Number of times two keys are compared	Determines the lower bound for comparison-based sorts
Swaps / moves	Number of times elements exchange or shift positions	Determines data-movement cost, relevant for large records
Pass	One sweep over the (remaining) array	Used to count iterations in bubble and selection sort
Inversion	A pair $(i, j)$ with $i < j$ but $a [i] > a [j]$	Equals the swap count of bubble sort and the shift count of insertion sort
Stable	Equal keys keep their original relative order	Matters when records are sorted by one field but carry other data
In-place	$O (1)$ extra storage outside the input (recursion stack reported separately)	Matters for memory-constrained sorting

LOWER BOUND FOR COMPARISON-BASED SORTING

C_{worst} (n) \geq ⌈ lo g_{2} (n!)⌉ = Ω (n lo g n)

Any sort that learns about the keys only by comparing pairs of them must make $Ω (n lo g n)$ comparisons in the worst case, and also on average. Proof idea: there are $n!$ possible orderings of $n$ distinct keys. A binary decision tree that distinguishes them all has at least $n!$ leaves, so its height is at least $⌈ lo g_{2} (n!)⌉$ , and $lo g_{2} (n!) = Θ (n lo g n)$ by Stirling's approximation.

EXAM TIP

This lower bound applies only to comparison-based sorts. Counting sort and radix sort beat it because they use the key values directly, as array indices or extracted digits, instead of comparing pairs. This is not a contradiction: it is exactly why they are called non-comparison sorts, and why they need extra conditions on the keys.

3. Elementary O(n^2) sorts: bubble, selection, insertion

All three are quadratic in the worst case. They differ in how their cost depends on the input, whether they are stable, and how many swaps they make compared with comparisons. Questions often probe exactly these differences rather than just the complexity class.

Bubble, selection and insertion sort compared (n elements; standard versions: bubble sort compares $n-i$ adjacent pairs in pass $i$)

Algorithm	Comparisons (worst)	Swaps / shifts (worst)	Passes	Stable	In-place	Best case
Bubble sort	$\frac{n ( n - 1 )}{2}$	$\frac{n ( n - 1 )}{2}$ swaps (reverse-sorted input); in general, swaps = number of inversions	$n - 1$ (fewer with an early-exit flag)	Yes	Yes	$O (n)$ only with an early-exit flag: one pass of $n - 1$ comparisons on sorted input
Selection sort	$\frac{n ( n - 1 )}{2}$ on every input	At most $n - 1$ swaps (one per pass)	$n - 1$	No (swap version)	Yes	$O (n^{2})$ : the comparison count does not depend on input order
Insertion sort	$\frac{n ( n - 1 )}{2}$	$\frac{n ( n - 1 )}{2}$ shifts; in general, shifts = number of inversions	$n - 1$	Yes	Yes	$O (n)$ : $n - 1$ comparisons and 0 shifts on sorted input

NUMBER OF INVERSIONS

0 \leq I \leq \frac{n ( n - 1 )}{2}, E [I] = \frac{n ( n - 1 )}{4}

The maximum occurs for reverse-sorted input. The expected value is for a uniformly random permutation of $n$ distinct keys, since each of the $(2 n)$ pairs is inverted with probability $\frac{1}{2}$ . Insertion sort runs in $Θ (n + I)$ time, so it is fast on nearly sorted input.

Selection sort's defining property is that its comparison count is input-independent. It always scans the whole unsorted part to find the minimum, so its best-case and worst-case comparison counts are both $\frac{n ( n - 1 )}{2}$ . Bubble sort (with an early-exit flag) and insertion sort, by contrast, finish in linear time on already-sorted data.

Insertion sort procedure (0-indexed, in place, ascending)

For i = 1 to n - 1, let key = a[i].
Set j = i - 1.
While j >= 0 and a[j] > key: shift a[j] to a[j + 1] and decrement j.
Place key at a[j + 1].
After each iteration the prefix a[0..i] is sorted. The strict > is what makes the sort stable.

The C version below follows the convention stated in Section 2.

void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

WORKED EXAMPLE · BUBBLE SORT TRACE

Sort [4, 2, 5, 1] ascending with standard bubble sort: in pass $i$ ( $i = 1, 2, 3$ ), compare the adjacent pairs at positions $(0, 1), \dots, (n - i - 1, n - i)$ and swap if left > right. How many comparisons and swaps are made in total?

Solution

Pass 1 (3 comparisons): (4,2) swap → [2,4,5,1]; (4,5) no swap; (5,1) swap → [2,4,1,5]. 2 swaps; 5 is now in its final place.
Pass 2 (2 comparisons): (2,4) no swap; (4,1) swap → [2,1,4,5]. 1 swap.
Pass 3 (1 comparison): (2,1) swap → [1,2,4,5]. 1 swap.
Totals: $3 + 2 + 1 = 6 = \frac{4 \cdot 3}{2}$ comparisons and $2 + 1 + 1 = 4$ swaps.
Check the swaps against the inversions of [4,2,5,1]: (4,2), (4,1), (2,1), (5,1). That is 4 inversions, matching the swap count.
An early-exit flag saves nothing here, because pass 3 still performs a swap and $n - 1 = 3$ passes is the maximum anyway.

Answer: 6 comparisons and 4 swaps. The number of swaps always equals the number of inversions.

EXAM TIP

The standard swap-based selection sort is not stable. For example, sorting $[2_{a}, 2_{b}, 1]$ swaps 1 with $2_{a}$ and gives $[1, 2_{b}, 2_{a}]$ . A variant that inserts the minimum at position $i$ by shifting the intervening elements right, instead of swapping, is stable. Read the implementation a question describes before answering.

4. Efficient comparison sorts: merge sort, quicksort, heap sort

These three achieve $O (n lo g n)$ at least on average, using divide-and-conquer or a heap. Merge sort and heap sort achieve it in the worst case as well.

BALANCED DIVIDE-AND-CONQUER RECURRENCE (MERGE SORT)

T (n) = 2 T (\frac{n}{2}) + Θ (n) \Rightarrow T (n) = Θ (n lo g n)

This applies whenever a problem of size $n$ is split into 2 equal halves with linear combine cost. The recursion tree has $lo g_{2} n$ levels, each costing $Θ (n)$ in total.

QUICKSORT RECURRENCES

Worst (split 0 : n - 1): Constant-fraction split (0 < c < 1) : T (n) = T (n - 1) + Θ (n) \Rightarrow Θ (n^{2}) T (n) = T (c n) + T ((1 - c) n) + Θ (n) \Rightarrow Θ (n lo g n)

Even a lopsided but constant-fraction split, such as 1 : 9, gives $Θ (n lo g n)$ . Only a split that leaves a constant number of elements on one side at every level gives $Θ (n^{2})$ .

Merge sort, quicksort and heap sort compared

Algorithm	Best	Average	Worst	Extra space	Stable	In-place
Merge sort	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (n)$ auxiliary array	Yes	No (standard array version)
Quicksort	$O (n lo g n)$	$O (n lo g n)$	$O (n^{2})$	Recursion stack: $O (lo g n)$ average, $O (n)$ worst with naive recursion	No	Yes
Heap sort	$O (n lo g n)$	$O (n lo g n)$	$O (n lo g n)$	$O (1)$	No	Yes

COMPARISONS TO MERGE TWO SORTED LISTS

min (m, n) \leq C_{merge} (m, n) \leq m + n - 1

This is for the standard two-pointer merge of sorted lists of sizes $m$ and $n$ . The worst case $m + n - 1$ occurs when the lists interleave. The best case $min (m, n)$ occurs when every element of the shorter list is smaller than every element of the longer one.

Quicksort: Lomuto partition procedure (pivot = last element)

Choose pivot = a[high].
Set i = low - 1, the boundary of the elements known to be <= pivot.
For j = low to high - 1: if a[j] <= pivot, increment i and swap a[i] with a[j].
After the loop, swap a[i + 1] with a[high]. The pivot is now in its final sorted position i + 1.
Recursively sort the left part low .. i and the right part i + 2 .. high.

int partition(int a[], int low, int high) {
    int pivot = a[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (a[j] <= pivot) {
            i++;
            int t = a[i]; a[i] = a[j]; a[j] = t;
        }
    }
    int t = a[i + 1]; a[i + 1] = a[high]; a[high] = t;
    return i + 1;
}

void quicksort(int a[], int low, int high) {
    if (low < high) {
        int p = partition(a, low, high);
        quicksort(a, low, p - 1);
        quicksort(a, p + 1, high);
    }
}

EXAM TIP

Quicksort's $Θ (n^{2})$ worst case occurs on already-sorted or reverse-sorted input when the pivot is always the first or last element. Every partition is then maximally unbalanced (0 and $n - 1$ elements). With Lomuto partitioning it also occurs when all keys are equal, because every element satisfies a[j] <= pivot. A uniformly random pivot gives an expected $O (n lo g n)$ time on every input, but its worst case is still $O (n^{2})$ . Median-of-three removes the sorted-input worst case but gives no worst-case guarantee.

BINARY HEAP OPERATION COSTS (HEAP OF N ELEMENTS)

build-heap = O (n), insert = O (lo g n), extract-max = O (lo g n)

Bottom-up build-heap is $O (n)$ , not $O (n lo g n)$ , because most nodes sit near the bottom and sift down only a short distance. Heap sort is build-heap followed by $n - 1$ extract-max operations: $O (n) + O (n lo g n) = O (n lo g n)$ .

EXAM TIP

Of these three, heap sort is the only one that is both $O (n lo g n)$ in the worst case and uses $O (1)$ extra space. It is not stable. Merge sort is the stable one of the three, at the cost of $O (n)$ extra space.

5. Linear-time sorts: counting sort and radix sort

When the keys are integers in a known bounded range, sorting can beat the $Ω (n lo g n)$ comparison lower bound. The trick is not to compare keys at all but to use them as array indices.

COUNTING SORT COMPLEXITY

T (n, k) = O (n + k), extra space = O (n + k)

$n$ = number of elements; the keys are integers in $0.. k - 1$ . The sort is linear when $k = O (n)$ and degrades when $k$ is much larger than $n$ . It is stable when the output is filled by scanning the input from right to left, as below. It is not in-place.

RADIX SORT COMPLEXITY

T (n, d, k) = O (d \cdot (n + k))

$d$ = number of digits (passes) and $k$ = the range of one digit ( $k = 10$ for decimal digits, $k = 2$ for bits). Least-significant-digit radix sort applies a stable sort, usually counting sort, once per digit. The total is linear when $d$ is a constant and $k = O (n)$ . It is not in-place.

Counting sort procedure (keys in the range 0..k-1)

Create a count array C of size k, initialised to 0.
For each input element, increment C[value].
Turn C into prefix sums: C[i] += C[i - 1] for i = 1 to k - 1. Now C[i] is the number of elements <= i.
Scan the input from the last element to the first (this order is what makes the sort stable). Place each element at output position C[value] - 1, then decrement C[value].
The output array is sorted, and equal keys keep their relative input order.

WORKED EXAMPLE · COUNTING SORT TRACE

Sort [4, 1, 3, 1, 4] using counting sort (keys in the range 0 to 4, so $k = 5$ ).

Solution

Count array C (index 0..4): [0, 2, 0, 1, 2], i.e. two 1s, one 3 and two 4s.
Prefix sums: C = [0, 2, 2, 3, 5].
Input index 4 (value 4) goes to output[C[4] - 1] = output[4], and C[4] becomes 4.
Input index 3 (value 1) goes to output[C[1] - 1] = output[1], and C[1] becomes 1.
Input index 2 (value 3) goes to output[C[3] - 1] = output[2], and C[3] becomes 2.
Input index 1 (value 1) goes to output[C[1] - 1] = output[0], and C[1] becomes 0.
Input index 0 (value 4) goes to output[C[4] - 1] = output[3], and C[4] becomes 3.
Output: [1, 1, 3, 4, 4].

Answer: [1, 1, 3, 4, 4]. The 1 from input index 1 lands before the 1 from index 3, and the 4 from index 0 lands before the 4 from index 4, so the sort is stable.

EXAM TIP

Radix sort's correctness depends on the per-digit sort being stable. Sorting from the least significant digit to the most significant works only if elements with equal current digits keep the order the previous passes gave them. With an unstable per-digit sort the final output can be wrong.

6. Hashing: hash functions, chaining, open addressing, load factor

A hash table maps keys to array slots through a hash function $h (k)$ . When collisions are handled well, it gives expected $O (1)$ search, insert and delete. Questions on this topic typically ask (a) where a key lands under a given collision-resolution scheme, and (b) the expected number of probes under each scheme.

Common hash functions

Division method: $h (k) = k mod m$ . It is simple. $m$ is best chosen as a prime not close to a power of 2, so the result depends on all the bits of $k$ , not only the low-order ones.
Multiplication method: $h (k) = ⌊ m \cdot (k A mod 1)⌋$ for a constant $0 < A < 1$ . It is less sensitive to the choice of $m$ .

LOAD FACTOR

α = \frac{n}{m}

$n$ = number of keys stored, $m$ = number of slots. With chaining, $α$ can exceed 1. With open addressing every key needs its own slot, so $α \leq 1$ . The open-addressing formulas below need $α < 1$ , i.e. at least one free slot.

EXPECTED PROBES: SEPARATE CHAINING (SIMPLE UNIFORM HASHING, NEW KEYS INSERTED AT THE HEAD OF THEIR CHAIN)

E [unsuccessful] = α, E [successful] = 1 + \frac{α}{2} - \frac{α}{2 n} \approx 1 + \frac{α}{2}

These count the keys examined. An unsuccessful search walks the whole chain, whose expected length is $α$ . A successful search examines the target plus the keys inserted into the same chain after it. Including the $O (1)$ hash computation, both searches take $Θ (1 + α)$ time. In the worst case, when all $n$ keys hash to one slot, a search takes $Θ (n)$ .

EXPECTED PROBES: OPEN ADDRESSING UNDER UNIFORM HASHING (EVERY PROBE SEQUENCE EQUALLY LIKELY)

E [unsuccessful] \leq \frac{1}{1 - α}, E [successful] \leq \frac{1}{α} ln (\frac{1}{1 - α})

These are upper bounds, valid for $α < 1$ . Uniform hashing is an idealisation that double hashing approximates well. Linear and quadratic probing do worse because of clustering.

EXPECTED PROBES: LINEAR PROBING (APPROXIMATIONS FOR LARGE TABLES)

E [successful] \approx \frac{1}{2} (1 + \frac{1}{1 - α}), E [unsuccessful] \approx \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}})

Valid for $α < 1$ . The squared term in the unsuccessful case shows how quickly primary clustering hurts as the table fills up.

Chaining vs open-addressing variants ($i = 0, 1, 2, \dots$ is the probe number)

Scheme	Probe sequence	Clustering	Can n exceed m?	Deletion
Separate chaining	One linked list (or other structure) per slot	None (no probing)	Yes, $α$ can exceed 1	Simple: remove from the list
Linear probing	$h (k, i) = (h^{'} (k) + i) mod m$	Primary clustering: runs of occupied slots grow and merge	No	Needs a 'deleted' marker (tombstone), not 'empty'
Quadratic probing	$h (k, i) = (h^{'} (k) + c_{1} i + c_{2} i^{2}) mod m$	Secondary clustering: keys with the same start slot follow the same probe sequence	No	Same tombstone caveat
Double hashing	$h (k, i) = (h_{1} (k) + i \cdot h_{2} (k)) mod m$	Least clustering of the three; closest to uniform hashing	No	Same tombstone caveat

When the probe sequence reaches every slot

Linear probing always visits all $m$ slots.
Double hashing visits all $m$ slots exactly when $h_{2} (k)$ is relatively prime to $m$ for every key. Two standard ways to guarantee this: make $m$ prime and $1 \leq h_{2} (k) < m$ , or make $m$ a power of 2 and $h_{2} (k)$ always odd. If $h_{2} (k) mod m = 0$ , the sequence never leaves the first slot.
Quadratic probing need not visit every slot, so an insert can fail even when free slots exist. With $h (k, i) = (h^{'} (k) + i^{2}) mod m$ , $m$ prime and $α \leq \frac{1}{2}$ , an empty slot is always found.

WORKED EXAMPLE · QUADRATIC PROBING TRACE

Table size $m = 7$ , $h^{'} (k) = k mod 7$ , quadratic probing with $c_{1} = 0$ and $c_{2} = 1$ , so $h (k, i) = (h^{'} (k) + i^{2}) mod 7$ . Insert keys 15, 8, 1 and 22 in this order into an empty table. Where does 22 land?

Solution

$h^{'} (15) = 1$ . Slot 1 is empty, so 15 goes to slot 1.
$h^{'} (8) = 1$ . Slot 1 is occupied; $i = 1$ gives $(1 + 1) mod 7 = 2$ , which is empty, so 8 goes to slot 2.
$h^{'} (1) = 1$ . Slot 1 is occupied; $i = 1$ gives slot 2 (occupied); $i = 2$ gives $(1 + 4) mod 7 = 5$ , which is empty, so 1 goes to slot 5.
$h^{'} (22) = 22 mod 7 = 1$ . Slot 1 is occupied; $i = 1$ gives slot 2 (occupied); $i = 2$ gives slot 5 (occupied); $i = 3$ gives $(1 + 9) mod 7 = 3$ , which is empty, so 22 goes to slot 3.

Answer: Key 22 is stored in slot 3, after 3 collisions (slots 1, 2 and 5).

EXAM TIP

In open addressing, never mark a deleted slot as simply 'empty'. A later search for a key that was placed beyond that slot during a collision would stop at the 'empty' slot and wrongly report failure. Use a distinct 'deleted' (tombstone) marker instead: searches probe past it, and inserts may reuse it.

PREVIOUS-YEAR QUESTIONS

18 questions from the CS and DA papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2023 · GATE CSE 2022 · GATE CSE 2020 · GATE DA 2026 · GATE DA 2025 · GATE DA 2024

GATE 2026 CS1 Q.24

GATE 2026 · CS1Q.24 · 1 mark · MSQ

Consider a hash table $P [0, 1, \dots, 10]$ that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is $h (x) = (x + 7) mod 11$ .

Consider the following sequence of insertions performed on $P$ :

1, 13, 22, 15, 11, 24

Which of the following positions in the hash table is/are empty after these insertions are performed?

(A)
0
(B)
10
(C)
2
(D)
1

Answer and solution

GATE 2026 CS1 Q.24: answer and solution

See the question in the paper

Searching, sorting and hashing

1. Linear search and binary search

2. Sorting fundamentals: stability, in-place, and the comparison lower bound

3. Elementary O(n^2) sorts: bubble, selection, insertion

4. Efficient comparison sorts: merge sort, quicksort, heap sort

5. Linear-time sorts: counting sort and radix sort

6. Hashing: hash functions, chaining, open addressing, load factor

18 questions from the CS and DA papers

5 questions to test yourself