[prev in list] [next in list] [prev in thread] [next in thread] 

List:       freebsd-hackers
Subject:    Re: qsort switching to insertsort
From:       Pieter de Goeje <pieter () degoeje ! nl>
Date:       2016-11-28 13:55:35
Message-ID: eac02a2e-22c7-844a-c6dd-edab1ebfa76d () degoeje ! nl
[Download RAW message or body]

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

_______________________________________________
freebsd-hackers@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-hackers
To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@freebsd.org"
[prev in list] [next in list] [prev in thread] [next in thread]