Re: algorithmic complexity attacks and libc qsort()

[Abhinav Upadhyay <er.abhinav.upadhyay%gmail.com@localhost>]

On Thu, Jun 12, 2014 at 4:53 PM, Martin Husemann <martin%duskware.de@localhost> 
wrote:
> On Thu, Jun 12, 2014 at 01:14:59PM +0200, Thomas Klausner wrote:
>> Except if we want to improve it based on FreeBSD's version, that
>> switched to insertion sort in some cases and improves the best case
>> this way.
>
> A "qsort" function that does some other sort? I'd call that a bug (or
> benchmark cheating).

For already sorted or partially sorted arrays of small enough size,
insertion sort would perform better than quicksort. So when the
partitions created by quicksort are small enough, it can switch to
insertion sort. I think in case of an already sorted array, this would
avoid quick sort's worst case complexity of O(n^2).