I was reading about QuickSort and it appears that ideally, they used randomized algorithm for choosing a pivot with at least 25-75 split of the array. Why can't they calculate the median value of the array and choose the most nearest value to median in every recursive call?
I think it would take the same amount of running time or maybe even better than randomized approach.
Using median of medians, a near median can be chosen, but the overhead is significant, effectively sorting groups of 5. Wiki article:
https://en.wikipedia.org/wiki/Median_of_medians
Note that median of medians can be implemented in place.
As for a random pivot, the code to calculate a random index takes a significant amount of the time during a partition step.
A simpler approach is to use the median of first, middle, last, to avoid worst case time for already sorted or reverse sorted data, and as answered by yeputons, using introsort which switches to heap sort (based on level of recursion) to avoid worst case time.
Because calculating median value takes at least linear time (in comparison to constant time required for random selection), and it's no trivial in linear time. So even though asymptotical performance becomes guaranteed, wall clock performance decreases. I believe it's more practical to guarantee performance in other ways, e.g. by using Introsort.
