What element of the array would be the median if the the size of the array was even and not odd?

Question

I read that it's possible to make quicksort run at O(nlogn)

the algorithm says on each step choose the median as a pivot

but, suppose we have this array:

10 8 39 2 9 20

which value will be the median?

In math if I remember correct the median is (39+2)/2 = 41/2 = 20.5

I don't have a 20.5 in my array though

thanks in advance

Answer 1

You can choose either of them; if you consider the input as a limit, it does not matter as it scales up.

Answer 2

We're talking about the exact wording of the description of an algorithm here, and I don't have the text you're referring to. But I think in context by "median" they probably meant, not the mathematical median of the values in the list, but rather the middle point in the list, i.e. the median INDEX, which in this cade would be 3 or 4. As coffNjava says, you can take either one.