qsort switching to insertsort

[Mehmet Erol Sanliturk]

On Sat, Nov 26, 2016 at 4:27 AM, Tristan Verniquet <tris_vern at hotmail.com>
wrote:

> > 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
> _______________________________________________
>
>


In quick sort , it is necessary to check worst case and switch to another
sort method if it is detected .
When this is not done , end result is stack overflow , etc . , but not
success .
Therefore , it is not possible to eliminate an alternative sort method .


Mehmet Erol Sanliturk