"in" everywhere

[Sean Kelly]

Andrei Alexandrescu Wrote:
> 
> In fact, guards can be put to ensure that the _expected_ (not average, 
> not best-case) complexity is O(n log n). This makes the risk of hitting 
> a worst-case scenario negligible in a principled manner.
> 
> http://en.wikipedia.org/wiki/Quicksort#Randomized_quicksort_expected_complexity
> 
> http://docs.google.com/viewer?a=v&q=cache:MdBVR26N5UsJ:www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0123.pdf+randomized+quicksort&hl=en&gl=us&pid=bl&srcid=ADGEESi3GTSxfHWkeb_f14H0pkbigduS94qJVc9XLQ7aPa6lPUJ5JZbggI0izFe3ogiVOJCYcVkGtdumaS9hBvrGw0-TA_yZQj2qd1-AEudKyEWEGXnO4sTwqCZL95OpFkdFHDF2WXFV&sig=AHIEtbT1R0q5RIR4rob17QUKlYVl90vXyQ
> 
> Currently std.algorithm.getPivot picks the middle of the range as the 
> pivot, but I made it modular such that it can be improved in a number of 
> ways (i.e. randomized, median-of-3, median-of-5, etc).

It would be nice if it used insertion sort for small ranges as well.  There's also a quicksort variant that partitions equal-to elements separately from less-than and greater-than values, which is faster for ranges with a lot of equal elements (and no slower for ranges without).