From owner-freebsd-current@freebsd.org  Tue Apr 19 08:44:23 2016
Return-Path: <owner-freebsd-current@freebsd.org>
Delivered-To: freebsd-current@mailman.ysv.freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org
 [IPv6:2001:1900:2254:206a::19:1])
 by mailman.ysv.freebsd.org (Postfix) with ESMTP id F0021B118F3
 for <freebsd-current@mailman.ysv.freebsd.org>;
 Tue, 19 Apr 2016 08:44:23 +0000 (UTC)
 (envelope-from afiskon@devzen.ru)
Received: from relay08.nicmail.ru (relay08.nicmail.ru [195.208.6.4])
 (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits))
 (Client did not present a certificate)
 by mx1.freebsd.org (Postfix) with ESMTPS id A7D1919E2
 for <freebsd-current@freebsd.org>; Tue, 19 Apr 2016 08:44:23 +0000 (UTC)
 (envelope-from afiskon@devzen.ru)
Received: from [109.70.25.225] (port=47293 helo=fujitsu)
 by f17.mail.nic.ru with esmtp (Exim 5.55)
 (envelope-from <afiskon@devzen.ru>)
 id 1asR7o-0006it-41; Tue, 19 Apr 2016 11:35:12 +0300
Received: from [93.174.131.138] (account afiskon@devzen.ru HELO fujitsu)
 by proxy03.mail.nic.ru (Exim 5.55)
 with id 1asR7o-0003Iy-56; Tue, 19 Apr 2016 11:35:12 +0300
Date: Tue, 19 Apr 2016 11:34:30 +0300
From: Aleksander Alekseev <afiskon@devzen.ru>
To: Warren Block <wblock@wonkity.com>
Cc: Hans Petter Selasky <hps@selasky.org>, FreeBSD Current
 <freebsd-current@freebsd.org>
Subject: Re: qsort() documentation
Message-ID: <20160419113430.69e41a0b@fujitsu>
In-Reply-To: <alpine.BSF.2.20.1604181250450.68720@wonkity.com>
References: <5714C86A.8050204@selasky.org>
 <alpine.BSF.2.20.1604181250450.68720@wonkity.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
X-BeenThere: freebsd-current@freebsd.org
X-Mailman-Version: 2.1.21
Precedence: list
List-Id: Discussions about the use of FreeBSD-current
 <freebsd-current.freebsd.org>
List-Unsubscribe: <https://lists.freebsd.org/mailman/options/freebsd-current>, 
 <mailto:freebsd-current-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-current/>
List-Post: <mailto:freebsd-current@freebsd.org>
List-Help: <mailto:freebsd-current-request@freebsd.org?subject=help>
List-Subscribe: <https://lists.freebsd.org/mailman/listinfo/freebsd-current>, 
 <mailto:freebsd-current-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Tue, 19 Apr 2016 08:44:24 -0000

> 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.
"""

-- 
Best regards,
Aleksander Alekseev
http://eax.me/