Sorting – GATE CSE AlgorithmsPractice Questions & PYQs

Build phase (\texttt{BUILD-MAX-HEAP}$): calls$\texttt{MAX-HEAPIFY}$on each non-leaf node =$\lfloor n/2 \rfloor$calls. **Sort phase**: for each of the$n-1$iterations, swaps the root with the last element and calls$\texttt{MAX-HEAPIFY}$once =$n-1$calls. Total =$\lfloor n/2 \rfloor + (n-1)$ calls. Options B and C are equivalent expressions for the same value.

In max heap, parent ≥ children. Only option B satisfies heap property.

Hash values: 18 mod13=5, 41 mod13=2, 22 mod13=9, 44 mod13=5(collision1→chain at slot5), 59 mod13=7, 32 mod13=6, 31 mod13=5(collision2→chain at slot5), 73 mod13=8. Collisions: 44 collides with 18 at slot 5 (collision 1), 31 collides at slot 5 (collision 2). Total collisions = 2.

Merge sort on a linked list does not require $O(n)$ auxiliary space for merging, because two sorted linked lists can be merged in $O(1)$ extra space by relinking pointers. The recursion stack uses $O(\log n)$ space. Hence time $= O(n \log n)$ and space $= O(\log n)$ for the call stack. This is one reason merge sort is preferred over quick sort for linked lists.

A: With m = 2^p, the multiplication method reduces to extracting p bits from k×A - efficiently implemented with bit shifts and multiplication. B: Knuth recommends A = (√5-1)/2 ≈ 0.618 (golden ratio conjugate) as it distributes keys uniformly due to its irrational nature. C: Unlike the division method (where m must be chosen carefully as a prime), the multiplication method works reasonably well for any m, giving more flexibility. D: FALSE - neither method universally outperforms the other; performance depends on the key distribution.

In a min-heap, the root always contains the minimum element of the entire array. Regardless of the order in which $\texttt{BUILD-MIN-HEAP}$ processes the elements, the resulting heap always places the global minimum at the root. The minimum of $\{3, 1, 4, 1, 5, 9, 2, 6\}$ is $1$, so the root will be $1$ after building the min-heap.

For a constant ratio split $1:9$, the recurrence is $T(n) = T(n/10) + T(9n/10) + O(n)$. The recursion tree has depth $\log _{10/9} n = O(\log n)$ (since $10/9 > 1$ is a constant). Each level does $O(n)$ work. Hence $T(n) = O(n \log n)$. Any constant ratio split (no matter how unbalanced, as long as it is a fixed fraction) gives $O(n \log n)$. Only a ratio that grows with $n$ (like $1:(n-1)$) gives $O(n^2)$.

To merge two sorted arrays each of size $n/2$: in the worst case, elements are perfectly interleaved (e.g., $[1, 3, 5, \ldots]$ and $[2, 4, 6, \ldots]$). We alternate comparisons until all but one element of one array remains, requiring $(n/2 - 1) + (n/2) = n - 1$ comparisons. The last remaining element is appended without comparison. Hence at most $n - 1$ comparisons.

This is the classic CLRS linear probing example. Final table positions: 10→slot10(1 probe), 22→slot0(1), 31→slot9(1), 4→slot4(1), 15→slot5(1), 28→slot6(1), 17→slot7(1), 88→slot1(2 probes: h=0 taken→1), 59→slot2(3 probes: h=4 taken→5 taken→... wait h(59)=4, slot4 taken→5 taken→6 taken→7 taken→8, 4 probes). Recount for CLRS example: standard result gives average ≈ 2.0 probes.

Deleting the minimum (root) involves: (1) Replace root with the last element - $O(1)$. (2) Remove the last element - $O(1)$. (3) Heapify-down (sift-down): repeatedly swap with the smaller child until the heap property is restored. The height of the heap is $\lfloor \log_2 n \rfloor$, so at most $O(\log n)$ swaps are needed.

Insert 10: $[10]$. Insert 20: $[10, 20]$ (20 > parent 10, no swap). Insert 15: $[10, 20, 15]$ (15 > parent 10, no swap). Insert 30: $[10, 20, 15, 30]$ (30 > parent 20, no swap). Insert 40: $[10, 20, 15, 30, 40]$ (40 > parent 20, no swap). Since each new element was larger than its parent, no heapify-up swaps were needed. Final min-heap: $[10, 20, 15, 30, 40]$. Verify: $10 \leq 20, 15$ ✓; $20 \leq 30, 40$ ✓; $15$ is a leaf ✓.

The worst case for quick sort occurs when the pivot always partitions the array into subarrays of sizes $0$ and $n-1$ - e.g., always picking the smallest or largest element as pivot on a sorted or reverse-sorted array. The recurrence becomes $T(n) = T(n-1) + T(0) + O(n) = T(n-1) + O(n)$, which solves to $T(n) = O(n^2)$.

Universal hashing prevents adversarial worst-case collisions.

Track insertions and load factor: m=8, threshold α=0.75 → rehash when n/m > 0.75 → when n > 6. After inserting 7th key: α=7/8=0.875>0.75 → rehash to m=16 (rehash #1). Continue inserting. After inserting 13th key into m=16: α=13/16=0.8125>0.75 → rehash to m=32 (rehash #2). But we only insert 12 keys total. After 7th key: rehash to m=16. Insert keys 8-12 (5 more): n=12, α=12/16=0.75 - not strictly greater than 0.75, so no second rehash. Total rehashing operations = 1. But if threshold is α ≥ 0.75 (greater than or equal): rehash when n=6 (α=6/8=0.75): rehash to m=16; then n=12: α=12/16=0.75 → rehash to m=32. Total = 2 rehashes.

The recurrence $C(n) = 2C(n/2) + n/2$ has $a = 2$, $b = 2$, $f(n) = n/2 = \Theta(n)$. Since $n^{\log_b a} = n^1 = \Theta(n) = \Theta(f(n))$, by Master theorem Case 2: $C(n) = \Theta(n \log n)$. The constant factor is smaller than worst case (best case uses $n/2$ comparisons per merge instead of $n-1$), but the asymptotic complexity is still $\Theta(n \log n)$.

For sorted $[1,2,3,4,5]$ with last element as pivot (Lomuto): each partition step places the pivot (last element) at its correct position with 1 final swap. Step 1: Pivot $= 5$. Scan $[1,2,3,4]$ - all $< 5$, $i$ ends at 3. Swap $A[4] \leftrightarrow A[4]$ (1 swap, self-swap). Step 2: Pivot $= 4$ on $[1,2,3,4]$. All $< 4$, swap $A[3] \leftrightarrow A[3]$ (1 swap). Step 3: Pivot $= 3$, 1 swap. Step 4: Pivot $= 2$, 1 swap. Step 5: Single element, no swap. Total swaps $= \mathbf{4}$.

A complete binary tree of height $h$ has at most $2^{h+1} - 1$ nodes (when all levels are completely filled). Level 0 (root) has $2^0 = 1$ node, level 1 has $2^1 = 2$ nodes, ..., level $h$ has $2^h$ nodes. Total $= \sum_{i=0}^{h} 2^i = 2^{h+1} - 1$.

The time complexity of Merge Sort in the worst-case scenario is O(n log n). For n=64, the complexity is O(64 log 64) which evaluates to O(64).

In a max-heap, the second largest element must be a child of the root (since the largest is the root, and only elements along the path from root can be displaced). The root has at most 2 children, so naively the second largest is among the root's children and the root of the right subtree - but more precisely, the second largest must be one of the $O(\log n)$ nodes on the path from root to a leaf (or among root's children). Since the root has 2 children and $\log n$ ancestors could beat it... the answer is $\Theta(\log n)$ - we only need to check nodes at most $O(\log n)$ levels deep.