Date: Mon, 28 Nov 2016 14:55:35 +0100 From: Pieter de Goeje <pieter@degoeje.nl> To: Hans Petter Selasky <hps@selasky.org>, Tristan Verniquet <tris_vern@hotmail.com>, freebsd hackers <freebsd-hackers@freebsd.org> Subject: Re: qsort switching to insertsort Message-ID: <eac02a2e-22c7-844a-c6dd-edab1ebfa76d@degoeje.nl> In-Reply-To: <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> References: <ME1PR01MB0546A92343D712D8439B299C83880@ME1PR01MB0546.ausprd01.prod.outlook.com> <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org>
next in thread | previous in thread | raw e-mail | index | archive | help
Op 2016-11-26 om 11:51 schreef Hans Petter Selasky: > 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. qsort() can easily be fixed to always work O(n log n) worst case time by falling back to heapsort if a pathological case is detected. This is called introsort (introspection sort). See https://en.wikipedia.org/wiki/Introsort for a description. The TL;DR is that quicksort should fall back to heapsort if the recursion depth exceeds 2*log n. -- Pieter de Goeje
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?eac02a2e-22c7-844a-c6dd-edab1ebfa76d>