Sorting – GATE CSE AlgorithmsPractice Questions & PYQs

The time complexity of binary search is $O(\log n)$, linking (A) to (R). Merge sort consistently performs at $O(n \log n)$, linking (C) to (S). Insertion sort has a worst-case time complexity of $O(n^2)$, linking (D) to (Q). By process of elimination, (B) maps to (P), which constitutes the provided target answer.

In QuickSort using the first element as the pivot, the partitioning step compares the pivot with all $n-1$ remaining elements.
For input (i), $1, 2, \dots, n$, the pivot $1$ is the smallest, resulting in $n-1$ comparisons and a sub-problem of size $n-1$.
For input (ii), $n, n-1, \dots, 1$, the pivot $n$ is the largest, also resulting in $n-1$ comparisons and a sub-problem of size $n-1$.
Both scenarios follow the same recurrence $T(n) = T(n-1) + (n-1)$, which yields $T(n) = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}$.
Therefore, $C_1 = C_2$.

Merge sort follows the divide and conquer paradigm, which splits an array of size $n$ into two halves. The process consists of three distinct stages: dividing the input, conquering subproblems via recursion, and combining the sorted results. The algorithm's time complexity is described by the recurrence relation $T(n) = 2T(n/2) + O(n)$, where $O(n)$ represents the linear time required to merge two sorted sub-arrays. By recursively partitioning the data into smaller, manageable subproblems and subsequently merging them, the algorithm solves the original problem efficiently. This mechanism is the classic definition of the divide and conquer strategy.

Comparison-based sorting algorithms like Heap sort, Quick sort, and Merge sort have a theoretical lower bound of $\Omega(n \log n)$ and cannot achieve $O(n)$ time. Radix sort performs sorting by processing individual digits. For $n$ numbers in the range $[1 \dots n^3]$, we can represent each number in base $n$. Since the maximum value is $n^3$, the number of digits $d$ required is $\log_n(n^3) = 3$. The complexity of Radix sort is $O(d(n+b))$, where $d$ is the number of digits and $b$ is the base. Setting $b=n$ and $d=3$, the complexity becomes $O(3(n+n)) = O(n)$, which satisfies the requirement.

For a comparison-based sorting algorithm with $n$ elements, the number of possible permutations is $n!$. We model this process using a decision tree of height $h$, where each node represents a comparison, implying $2^h \ge n!$. Taking the logarithm on both sides gives $h \ge \log_2(n!)$, and by Stirling's approximation, $\log_2(n!) = \Theta(n \log n)$. Thus, the worst-case lower bound is $\Omega(n \log n)$. Since efficient algorithms like Merge Sort achieve this bound, the optimal complexity is $\Theta(n \log n)$.

Quicksort exhibits its worst-case time complexity of $O(n^2)$ when the pivot consistently results in highly unbalanced partitions, which occurs with sorted or reverse-sorted inputs using standard pivot selection (e.g., first or last element). For an input of size $n$, the number of comparisons is given by $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2}$.

For the input $[1, 2, 3, 4]$ where $n=4$:
$t_{1} \propto \frac{4(3)}{2} = 6$
For the input $[5, 4, 3, 2, 1]$ where $n=5$:
$t_{2} \propto \frac{5(4)}{2} = 10$
Since $6 < 10$, it follows that $t_{1} < t_{2}$.

If the pivot is always placed correctly, each partitioning step divides the problem into two subproblems of size roughly n/2. This leads to a recursion tree similar to Merge Sort, resulting in O(n log n) complexity.

If the pivot selection consistently leads to unbalanced partitions, the recursion depth becomes linear, resulting in O(n^2) time complexity. This is the worst-case scenario for Quick Sort. Options A and C accurately reflect this.

Choosing the first or last element as the pivot consistently can lead to the worst-case scenario if the array is already sorted or nearly sorted. This is because it can result in highly unbalanced partitions.

In the best case, each partitioning step divides the array into two subarrays. The minimum number of comparisons required to sort an array of size 5 is 7.

Choosing the median-of-three as the pivot helps to mitigate the worst-case scenario by reducing the probability of selecting a pivot that consistently leads to unbalanced partitions.

When the smallest element is consistently chosen as the pivot, the partitioning will result in one subarray of size 0 and another of size (n-1). This leads to a recursive structure similar to insertion sort, resulting in O(n^2) complexity in the worst case.

No, the stability of the entire algorithm is determined by the weakest link in the chain. If the merge step is not stable, the overall sorting process will not be stable, even if the splitting step is.

In each partitioning step, we make comparisons equal to the size of the subarray minus one. For an array of size 5, the minimum comparisons would be 4 (for the first partitioning).

The space complexity of Merge Sort is primarily determined by the merging step, which requires additional space to store the merged subarrays. Even with a stable merge, the space complexity remains O(n) as it still needs to temporarily store the elements during the merge process.

Randomly selecting the pivot helps to reduce the probability of consistently choosing unfavorable pivots, minimizing the likelihood of encountering the worst-case scenario.