"in" everywhere

[Andrei Alexandrescu]

On 10/9/10 9:05 CDT, "Jérôme M. Berger" wrote:
> Seth Hoenig wrote:
>> 2010/10/8 "Jérôme M. Berger"<jeberger at free.fr>
>>
>>> Steven Schveighoffer wrote:
>>>> On Thu, 07 Oct 2010 16:23:47 -0400, Rainer Deyke<rainerd at eldwood.com>
>>>> wrote:
>>>>> I can't say I've ever cared about the big-O complexity of an operation.
>>>> Then you don't understand how important it is.
>>>          If big O complexity is so important, then why does everyone use
>>> quicksort (which is O(n**2)) and not heap sort or merge sort (which
>>> are O(n*log(n)))?
>>>
>>>                 Jerome
>>
>> Because on average quicksort is faster than heap sort, and uses much less
>> space than merge sort. Also, trivial guards can be put in place to avoid
>> running quicksort in a worst case (pre-sorted data) scenario.
>>
> 	I rest my case.
>
> 		Jerome

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).


Andrei