In selecting the pivot for QuickSort, which is the best choice for optimal partitioning?
(a) First element
(b) Last element
(c) Middle element
(d) Largest element
(e) Median
(f) Any of the above
Ans. (e) The median of the array. Choosing the median produces the most balanced possible partitions and gives QuickSort its optimal running time of O(n log n).
💡 Explanation:
The median is the value for which approximately half of the elements are smaller and the other half are larger. Therefore, using the median as the pivot divides the array into two nearly equal subarrays.
The resulting recurrence is:
T(n) = 2T(n/2) + O(n)
The recursion has approximately log2(n) levels, and each level performs O(n) partitioning work. Therefore:
O(n) × O(log n) = O(n log n)
The first, last, or middle-position element does not always represent the median value, so each can produce poor partitions for specially arranged inputs. Choosing the largest element always creates one empty partition and another partition of size n − 1, giving the worst-case complexity O(n2).
Note: Finding the exact median can itself require additional work. However, when considering partition quality alone, the median is the ideal pivot.
Memory tip: The best pivot is the value that divides the data as evenly as possible—the median.