Question

Which of the following is TRUE about the Quick Sort algorithm?

• A. It is a stable sorting algorithm.
• B. Its worst-case complexity is $O(n \log n)$.
• C. Its performance depends heavily on the choice of the pivot.
• D. It requires $O(n)$ auxiliary space for merging.

Hint:

To avoid the $O(n^2)$ worst-case, many implementations use a "Randomized Pivot" or the "Median-of-Three" rule to ensure a more balanced partition.

Answer 1

The Correct Option is C

Concept: Quick Sort is a highly efficient, divide-and-conquer sorting algorithm that works by selecting a "pivot" element and partitioning the array around it.
• Partitioning: Rearranging the array so that elements less than the pivot are on the left, and elements greater than the pivot are on the right.

Step 1: Evaluating Option (A) and (D).

• Stability: Quick Sort is generally not stable because the swapping of elements during partitioning can change the relative order of equal elements. (A) is false.
• Space: Quick Sort is an "in-place" sort. It doesn't need extra space for merging (unlike Merge Sort, which needs $O(n)$). (D) is false.

Step 2: Evaluating Option (B).
The average time complexity of Quick Sort is $O(n \log n)$. However, in the worst case (e.g., when the array is already sorted and the first/last element is always picked as the pivot), the complexity degrades to $O(n^2)$. Thus, (B) is false.

Step 3: Evaluating Option (C).
The efficiency of Quick Sort is entirely dependent on how well the pivot divides the array. If the pivot consistently splits the array into two nearly equal halves, the performance is $O(n \log n)$. If the pivot is always the smallest or largest element, performance drops to $O(n^2)$. This makes (C) correct.