Sorting – GATE CSE AlgorithmsPractice Questions & PYQs

With tail-call optimization (always recursing on the smaller half), the recursion depth is bounded by $O(\log n)$ in the worst case. This is because the smaller partition has at most $n/2$ elements - so the stack depth is at most $\log_2 n$. The larger partition is handled iteratively (via a loop), not added to the call stack. This reduces worst-case stack space from $O(n)$ to $O(\log n)$.

B: Secondary clustering occurs because any two keys with the same initial hash value h'(k) follow identical probe sequences, causing them to compete for the same slots. This is less severe than linear probing's primary clustering but still degrades performance. D: Quadratic probing with m prime and c₁=c₂=1/2 guarantees probing at least m/2 distinct slots, but does NOT guarantee probing all m slots for arbitrary constants c₁, c₂ and arbitrary m. Double hashing (with gcd(h₂(k),m)=1) guarantees all m slots are probed.

Heap sort algorithm: (1) Build-Max-Heap: convert the array into a max-heap in $O(n)$. (2) Sort: for $i$ from $n$ down to 2, swap $A[1]$ (max) with $A[i]$, reduce heap size by 1, call $\texttt{MAX-HEAPIFY}(A, 1)$ to restore the heap. This places the maximum at the end in each iteration, producing a sorted array. Total time: $O(n \log n)$.

Hash values: 50 mod 7=1, 700 mod 7=0, 76 mod 7=6, 85 mod 7=1(collision→2), 92 mod 7=1(collision→2→3), 73 mod 7=3(collision→4), 101 mod 7=3(collision→4→5→6→... wait: position 3 taken by 92, position 4 by 73, position 5 empty→101 goes to 5). Let me recompute: 50→1, 700→0, 76→6, 85→h=1 taken→2, 92→h=1 taken→2 taken→3, 73→h=3 taken→4, 101→h=3 taken→4 taken→5. Position of 101 = 5. Closest option: B=5.

Median-of-three avoids the simple sorted/reverse-sorted worst cases. However, there exist adversarial inputs (constructed using knowledge of the median-of-three strategy) that still produce $O(n^2)$ behaviour. Musser (1997) showed this and proposed introsort as a solution. (A) Randomly shuffled arrays behave well on average. (B) Sorted arrays are handled well by median-of-three. (D) All-identical arrays are handled well with three-way partitioning but median-of-three alone without three-way partitioning gives $O(n^2)$.

For double hashing to generate a full permutation of all m slots (i.e., probe every slot before repeating), h₂(k) must be relatively prime to m - that is, gcd(h₂(k), m) = 1. If gcd(h₂(k), m) = d > 1, the probe sequence cycles through only m/d distinct slots, missing d-1 out of every d slots. A common implementation uses m as a prime and h₂(k) = 1 + (k mod (m-1)), which ensures h₂(k) ∈ {1, ..., m-1} and gcd(h₂(k), m) = 1 when m is prime.

For $n = 7$ (complete binary tree with 3 levels): non-leaf nodes are at indices 1, 2, 3 (1-indexed). $\texttt{HEAPIFY}$ at index 3 (height 1): at most 2 comparisons (compare with 2 children, select max). $\texttt{HEAPIFY}$ at index 2 (height 1): at most 2 comparisons. $\texttt{HEAPIFY}$ at index 1 (height 2): at most 4 comparisons (2 at each level, propagate down). Total worst case = $2 + 2 + 4 = 10$ comparisons. (Each $\texttt{HEAPIFY}$ at height $h$ costs at most $2h$ comparisons.)

Merge Sort has a time complexity of O(n log n), making it more efficient for large datasets compared to Bubble Sort's O(n^2) complexity.

With chaining and simple uniform hashing, all operations take expected Θ(1 + α). If the number of keys n = O(m) - meaning α = n/m = O(1) is bounded by a constant - then 1 + α = O(1) and all operations run in expected O(1) time. This is the basis for hash tables achieving O(1) amortized operations in practice. Insert is O(1) (prepend to chain), search is O(1+α), delete is O(1+α) with doubly linked lists or O(α) with singly linked lists.

Merge Sort is inherently stable because during the merge step, it ensures that elements with the same value maintain their original order.

Using $C(n) = 2C(n/2) + (n-1)$, $C(1) = 0$: $C(2) = 1$. $C(4) = 2(1) + 3 = 5$. $C(8) = 2(5) + 7 = 17$. $C(16) = 2(17) + 15 = 34 + 15 = \mathbf{49}$. Alternatively: $C(n) = n\log_2 n - (n-1) = 16 \times 4 - 15 = 64 - 15 = 49$.

The recurrence for worst-case comparisons: $C(n) = 2C(n/2) + (n - 1)$, $C(1) = 0$. $C(2) = 2C(1) + 1 = 1$. $C(4) = 2C(2) + 3 = 2(1) + 3 = 5$. $C(8) = 2C(4) + 7 = 2(5) + 7 = \mathbf{17}$. Alternatively, $C(n) = n\log_2 n - (n - 1) = 8 \times 3 - 7 = 24 - 7 = 17$ comparisons in the worst case.

(A) TRUE: a complete binary tree with $n$ nodes has height $\lfloor \log_2 n \rfloor$. (B) TRUE: in a max-heap, the minimum element must be a leaf (since every non-leaf is $\geq$ its children, a non-leaf cannot be minimum unless all elements are equal). It can be any leaf, not necessarily a specific one. (C) TRUE: a descending-sorted array satisfies the max-heap property - $A[i] \geq A[2i]$ and $A[i] \geq A[2i+1]$ holds since $A$ is decreasing and parent index $<$ child index. All three are TRUE.

With this optimization, on a fully sorted array: at every level of recursion, the last element of the left half is $\leq$ the first element of the right half, so the merge step is skipped entirely ($O(1)$ check). The recursion still splits all the way down ($O(\log n)$ levels, $n$ total nodes), but each node does only $O(1)$ work. Total $= O(n)$ checks across all recursive calls, giving $O(n)$ on sorted input.

h(25) = 25 mod 7 = 4. Slot 4 is occupied by key 4. Probe i=1: (4 + 1) mod 7 = 5. Check slot 5 - is it occupied? h(30)=2, h(22)=1, h(11)=4, h(4)=4→probed to... let me re-examine. h(22)=1→slot1. h(30)=2→slot2. h(11)=4→slot4. h(4)=4→occupied→(4+1)mod7=5→slot5. Now insert 25: h(25)=4→occupied. i=1: (4+1)mod7=5→occupied. i=2: (4+4)mod7=1→occupied. i=3: (4+9)mod7=(13)mod7=6→empty. Slot 6. Answer: D=6.

Merging two arrays each of size $m = 4$: worst case $= m + m - 1 = 4 + 4 - 1 = 7$ comparisons. This occurs when elements interleave maximally and the last comparison is needed to determine which remaining element goes last. For $L = [2,5,8,12]$ and $R = [3,6,9,15]$: comparisons are $2$vs$3$, $3$vs$5$, $5$vs$6$, $6$vs$8$, $8$vs$9$, $9$vs$12$, $12$vs$15$ - exactly 7 comparisons.

When two keys map to same index → collision.

When the array is already sorted in ascending order and the first element is always chosen as pivot: the first element is always the minimum, so the partition produces subarrays of sizes $0$ and $n-1$. This is the worst-case scenario for quick sort. The recurrence $T(n) = T(0) + T(n-1) + O(n)$ solves to $T(n) = O(n^2)$.

Step 1: Full array $[3, 1, 2]$, pivot $= 2$. Comparisons: $3$ vs $2$, $1$ vs $2$ = 2 comparisons. After partition: $[1, 2, 3]$, pivot at index 1. Step 2: Left subarray $[1]$ - size 1, 0 comparisons. Right subarray $[3]$ - size 1, 0 comparisons. Total comparisons $= 2 + 0 + 0 = \mathbf{3}$. (Each element except pivot is compared with pivot once in Lomuto.)