JuliaLang/julia — comment on commit ba883959b8ebbc9ea6488bbeb387220c7a8bbf58
File:  line 0
By StefanKarpinski:

A couple of tests. Using the following pivots, I get this performance:

- `(a[lo]+a[hi])/2`: 1.14x
- `a[div(lo+hi,2)]`: 1.15x
- `(a[lo]+a[hi]+a[div(lo+hi,2)])/3`: 1.16x
- `_jl_pivot_middle(a[lo],a[hi],a[div(lo+hi,2)])`: 1.23x
- `a[randival(lo,hi)]`: 1.28x

where `_jl_pivot_middle(a,b,c) = a < b ? (b < c ? b : c) : (a < c ? a : c)`. The _jl_pivot_middle choice is the best in terms of handling various pre-sorted orderings, but the average ones are almost as good. The trouble with averaging elements is that it doesn't work for general sorting because you can't generally do arithmetic with sort elements. However, we *only* use quicksort for array types that are Real, so this actually makes sense for us. The average-of-three is probably the best combination of high performance and resilience to different sort orders.