Sorting – GATE CSE AlgorithmsPractice Questions & PYQs

A: TRUE - uniform distribution minimizes collisions and chain lengths. B: TRUE - in the worst case (all n keys hash to the same slot), the chain length is n, and search takes O(n). This is why average-case or expected-case analysis is used for hash tables. C: FALSE - hash tables with chaining or open addressing have O(1) expected time but O(n) worst-case time. Perfect hashing achieves O(1) worst case. D: TRUE - universal hashing picks a random function from a universal family, ensuring that regardless of the key set chosen by an adversary, the expected number of collisions at any slot is at most 1 + α, giving O(1) expected search time.

Array-based merge sort requires: (1) Auxiliary array: $O(n)$ space for temporary storage during the merge step. (2) Recursion stack: $O(\log n)$ space for the call stack. The dominant term is $O(n)$ from the auxiliary array. Hence total space complexity $= O(n)$. Note: bottom-up (iterative) merge sort still needs $O(n)$ auxiliary space for merging.

(A) TRUE: Merge sort accesses data sequentially during merging - ideal for disk-based storage where sequential access is much faster than random access. (B) FALSE: Quick sort requires random access (pivot comparisons across the array) - very inefficient for external sorting. Merge sort is the standard choice. (C) TRUE: External merge sort Phase 1 creates sorted runs of size $M$ in memory; Phase 2 merges them using $k$-way merge. (D) TRUE: This is the standard I/O complexity of external merge sort from the I/O model (Aggarwal-Vitter model).

(A) TRUE: Standard quick sort is not stable - elements equal to the pivot can be reordered during partitioning. (B) TRUE: Best case is when pivot always produces balanced partitions, giving $T(n) = 2T(n/2) + O(n) = O(n \log n)$. (C) TRUE: Best/average case recursion depth is $O(\log n)$ (balanced splits), so the stack uses $O(\log n)$ space. Worst case stack is $O(n)$. (D) FALSE: On a sorted array with first-element pivot, quick sort does $O(n^2)$ comparisons while merge sort does $O(n \log n)$ - quick sort performs more comparisons here.

Primary clustering is the main disadvantage of linear probing. When a key hashes to a position in a cluster (a consecutive run of occupied slots), it extends the cluster by one. This causes long runs of occupied slots to grow longer over time, as any new key hashing anywhere in the cluster must probe to the end. This makes both insertion and search slower as the table fills. Quadratic probing reduces primary clustering but introduces secondary clustering. Double hashing largely eliminates clustering.

For the division method h(k) = k mod m, choosing m as a prime number that is not close to a power of 2 or 10 distributes keys most uniformly. If m is a power of 2, h(k) depends only on the low-order bits of k, ignoring higher bits and causing clustering for certain key distributions. A prime m ensures that the hash function depends on all bits of k, reducing collision probability. m = 97 satisfies both conditions: prime and not near 2^6 = 64 or 2^7 = 128.

Standard merge sort always divides and merges regardless of input order - it does not check if the array is already sorted. Thus, its time complexity is $\Theta(n \log n)$ even for sorted input. (Note: optimized versions like Timsort detect sorted runs and skip merging when $A[\text{mid}] \leq A[\text{mid}+1]$, achieving $O(n)$ on sorted input, but standard merge sort does not do this.)