qsort() documentation

[Warren Block]

On Tue, 19 Apr 2016, Aleksander Alekseev wrote:

>> Why Wikipedia, specifically?  There are a lot of places that describe
>> quicksort.  How about just
>>
>>    Note: This implementation of qsort() is designed to avoid the
>>    worst-case complexity of N**2 that is often seen with standard
>>    versions.
>
> I would say that this statement is just false. Worst-case complexity is
> still N**2. How about something like:
>
> """
> This implementation of qsort() has worst case complexity of N**2.
> However measures were taken that make it very unlikely that for some
> random input N**2 swaps will be made. It's still possible to generate
> such an input on purpose though. See code below for more details.
> """

Okay:

   The quicksort algorithm worst-case is O(N**2), but this implementation
   has been designed to avoid that for most real data.