qsort switching to insertsort

[Pieter de Goeje]

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