Date: Sat, 26 Nov 2016 06:35:53 -0800 From: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> To: Tristan Verniquet <tris_vern@hotmail.com> Cc: Hans Petter Selasky <hps@selasky.org>, freebsd hackers <freebsd-hackers@freebsd.org> Subject: Re: qsort switching to insertsort Message-ID: <CAOgwaMvUE%2BK==OE3zkpfpXa5kBC1YT4JAUVhujxEt9PcHXgqTw@mail.gmail.com> In-Reply-To: <ME1PR01MB0546D041DC160763C5D3689883880@ME1PR01MB0546.ausprd01.prod.outlook.com> References: <ME1PR01MB0546A92343D712D8439B299C83880@ME1PR01MB0546.ausprd01.prod.outlook.com> <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> <ME1PR01MB0546D041DC160763C5D3689883880@ME1PR01MB0546.ausprd01.prod.outlook.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sat, Nov 26, 2016 at 4:27 AM, Tristan Verniquet <tris_vern@hotmail.com> wrote: > > From: Hans Petter Selasky <hps@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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAOgwaMvUE%2BK==OE3zkpfpXa5kBC1YT4JAUVhujxEt9PcHXgqTw>