qsort switching to insertsort

[Tristan Verniquet]

> From: Hans Petter Selasky <hps at selasky.org>
> Sent: Saturday, 26 November 2016 8:51 PM
> To: Tristan Verniquet; freebsd hackers
> Subject: Re: qsort switching to insertsort
>    
> On 11/26/16 11:26, Tristan Verniquet wrote:
>> The easiest way forward for us is probably to comment out the offending code.
>>
> 
> Commenting out the offending code does not help. It simply leaves for 
> another type of dataset to provide the same behaviour. qsort() is doomed 
> in this regard.
> 
> --HPS

I can see that from, say, a security perspective, as long as a worst-case exists you would assume it, and so this would make no difference.

But from an everyday usage where security is not such an issue, I see the two worst-case triggers as being in different ball park. I would happily assume I'd never meet an accidental case of triggering a qsort worst-case based on pivot given the pivot selection method it uses, but can no longer have that confidence with qsort triggering an insertsort.

I was kind of suspecting that this might be the reasoning behind it. For example the second link shows problems with all quicksorts. But do you not think this makes a big difference in the everyday use case where qsort would actually be used (and not avoided)?

Tristan