# Why is the optimal choice for a pivot in quicksort algorithm the median element?

Lately i have been taking an course at brilliant.org, i was exploring a lesson on QuickSort algorithm, found a question.

Which of the following would provide the optimal pivot selection at each step of quicksort?

• A. The element in the first position
• B. The element with the smallest value
• C. A randomly selected element
• D. The median of the elements

The answer listed was "D"

but in real life arrays how is it going to be any of the options above?

Justification listed was

"the median value, will allow the algorithm to split the list into approximately equal parts, so the runtime will speed up."

We never know the value of a element, if we do choose a median how is it guaranteed to make the array split into 2 parts ? For all we know it may turn out of be the highest or lowest or very near to the highest or the lowest number. Which would make either of the left array or right array almost empty.

• By the definition of median, the optimal pivot point is the median i.e. that there is equal probability of a value being above or below it. Now, it's true that it's often more expensive to find the median than to approximate it but that doesn't make the answer wrong. Just not always practical. – Alex Sep 25 '17 at 10:26
• The chosen element divides the problem in two. You want BOTH halfs to be as small as possible to minimize the problem - that means that you should make them exactly half if you can. – Thorbjørn Ravn Andersen Sep 26 '17 at 12:05