"in" everywhere

[Andrei Alexandrescu]

On 10/9/10 11:52 CDT, Sean Kelly wrote:
> 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).

I guess that's "fit pivot" :o). Fat pivot does cost some more.

Andrei