✏️ Explanatory Question
If the middle element is always chosen as the pivot in QuickSort, does this make it unlikely that QuickSort will require quadratic time?
If the middle element is always chosen as the pivot in QuickSort, does this make it unlikely that QuickSort will require quadratic time?
Ans. No. Choosing the middle-position element as the pivot does not guarantee that quadratic time will be avoided. A specially arranged input can make that pivot the smallest or largest value during every recursive call, producing highly unbalanced partitions. Therefore, the worst-case running time remains O(n2).
💡 Explanation:
The middle element refers to the element at the middle position of the current subarray; it is not necessarily the median value. A fixed pivot-selection rule can be defeated by a carefully constructed input.
If the selected pivot is repeatedly the smallest or largest value, one partition has size 0 while the other has size n − 1. This is the most unbalanced partition possible.
The recurrence is:
T(n) = T(n − 1) + O(n)
Expanding it gives:
n + (n − 1) + (n − 2) + … + 1 = n(n + 1)/2 = O(n2)
Thus, selecting the middle-position element may work well for many ordinary inputs, but it can never guarantee O(n log n) performance or eliminate the O(n2) worst case.
Memory tip: A middle-position pivot is not always the median. Balanced partitions produce O(n log n), while repeatedly unbalanced partitions produce O(n2).