Quicksort pivote choice

I've read that the pivote can be the median of 3 numbers, bottom, middle a开发者_Python百科nd top. But, could that generate overflow? What happens if the median returns a value larger than the array size? I assume that the this choice is by assuming that they array values can't be longer than the array size. I think I'm confused at what a pivote really is.

The pivot is just the value that you compare other values against - lower values go the left, higher to the right. The pivot can be chosen by taking any of the existing values in the array. If the array is completely unsorted, it won't matter which value you choose. If it is somewhat sorted, you should choose a value from the middle of the array.

UPDATE: Some reading informs me that a better pivot choice may be to choose the median value of 3 values in the array (such as middle, bottom and top or 3 random positions). Some people advocate taking the median of 5 values. The worst-case performance of quicksort occurs when pivot is close to the smallest or largest value in the array, and this tactic is intended to defend against that occurring. This is just an optimisation for certain kinds of data - it is not a necessity.