From owner-freebsd-current@freebsd.org  Wed Apr 20 04:01:35 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 1E2D9B15C94
 for <freebsd-current@mailman.ysv.freebsd.org>;
 Wed, 20 Apr 2016 04:01:35 +0000 (UTC)
 (envelope-from wblock@wonkity.com)
Received: from wonkity.com (wonkity.com [67.158.26.137])
 (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits))
 (Client CN "wonkity.com", Issuer "wonkity.com" (not verified))
 by mx1.freebsd.org (Postfix) with ESMTPS id DED471DDA
 for <freebsd-current@freebsd.org>; Wed, 20 Apr 2016 04:01:34 +0000 (UTC)
 (envelope-from wblock@wonkity.com)
Received: from wonkity.com (localhost [127.0.0.1])
 by wonkity.com (8.15.2/8.15.2) with ESMTPS id u3K41MLd023977
 (version=TLSv1.2 cipher=DHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO);
 Tue, 19 Apr 2016 22:01:22 -0600 (MDT)
 (envelope-from wblock@wonkity.com)
Received: from localhost (wblock@localhost)
 by wonkity.com (8.15.2/8.15.2/Submit) with ESMTP id u3K41KPs023974;
 Tue, 19 Apr 2016 22:01:21 -0600 (MDT)
 (envelope-from wblock@wonkity.com)
Date: Tue, 19 Apr 2016 22:01:20 -0600 (MDT)
From: Warren Block <wblock@wonkity.com>
To: Aleksander Alekseev <afiskon@devzen.ru>
cc: Hans Petter Selasky <hps@selasky.org>,
 FreeBSD Current <freebsd-current@freebsd.org>
Subject: Re: qsort() documentation
In-Reply-To: <20160419113430.69e41a0b@fujitsu>
Message-ID: <alpine.BSF.2.20.1604192002111.59174@wonkity.com>
References: <5714C86A.8050204@selasky.org>
 <alpine.BSF.2.20.1604181250450.68720@wonkity.com>
 <20160419113430.69e41a0b@fujitsu>
User-Agent: Alpine 2.20 (BSF 67 2015-01-07)
MIME-Version: 1.0
Content-Type: text/plain; format=flowed; charset=US-ASCII
X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.4.3
 (wonkity.com [127.0.0.1]); Tue, 19 Apr 2016 22:01:22 -0600 (MDT)
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: Wed, 20 Apr 2016 04:01:35 -0000

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.