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

Question

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.

Answer 1

You seem to be confusing the median value and the middle element.

The middle element of the unsorted array could indeed turn out to be close to the lowest or highest value.
The median value on the other hand is the value that has half the values compare as smaller and half the values compare as bigger.

The advantage of using the median value as a pivot in quicksort is that it guarantees that the two partitions are as close to equal size as possible.
The problem of using the median value is that you need to know the values of all elements to know which the median is. This makes using the median value hard to do in practice, despite it being the optimal value in theory.