From owner-freebsd-hackers@freebsd.org  Mon Nov 28 14:03:20 2016
Return-Path: <owner-freebsd-hackers@freebsd.org>
Delivered-To: freebsd-hackers@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 415E8C5948C
 for <freebsd-hackers@mailman.ysv.freebsd.org>;
 Mon, 28 Nov 2016 14:03:20 +0000 (UTC)
 (envelope-from pieter@degoeje.nl)
Received: from degoeje.nl (degoeje.nl [81.169.238.128])
 by mx1.freebsd.org (Postfix) with ESMTP id 0A1781363
 for <freebsd-hackers@freebsd.org>; Mon, 28 Nov 2016 14:03:19 +0000 (UTC)
 (envelope-from pieter@degoeje.nl)
Received: from [192.168.1.250] (unknown [188.203.228.182])
 by degoeje.nl (Postfix) with ESMTPSA id 3D8C215C013E;
 Mon, 28 Nov 2016 14:55:37 +0100 (CET)
Subject: Re: qsort switching to insertsort
To: Hans Petter Selasky <hps@selasky.org>,
 Tristan Verniquet <tris_vern@hotmail.com>,
 freebsd hackers <freebsd-hackers@freebsd.org>
References: <ME1PR01MB0546A92343D712D8439B299C83880@ME1PR01MB0546.ausprd01.prod.outlook.com>
 <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org>
From: Pieter de Goeje <pieter@degoeje.nl>
Message-ID: <eac02a2e-22c7-844a-c6dd-edab1ebfa76d@degoeje.nl>
Date: Mon, 28 Nov 2016 14:55:35 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101
 Thunderbird/45.5.0
MIME-Version: 1.0
In-Reply-To: <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Status: No, score=-1.0 required=3.5 tests=ALL_TRUSTED autolearn=ham
 autolearn_force=no version=3.4.0
X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on degoeje.nl
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.23
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
 <freebsd-hackers.freebsd.org>
List-Unsubscribe: <https://lists.freebsd.org/mailman/options/freebsd-hackers>, 
 <mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers/>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <https://lists.freebsd.org/mailman/listinfo/freebsd-hackers>, 
 <mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Mon, 28 Nov 2016 14:03:20 -0000

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