From owner-freebsd-current@freebsd.org Mon Apr 18 14:49:14 2016 Return-Path: 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 96F7AB13C2B for ; Mon, 18 Apr 2016 14:49:14 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: from mail-yw0-x230.google.com (mail-yw0-x230.google.com [IPv6:2607:f8b0:4002:c05::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 5A75C10B4 for ; Mon, 18 Apr 2016 14:49:14 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: by mail-yw0-x230.google.com with SMTP id j74so26876371ywg.1 for ; Mon, 18 Apr 2016 07:49:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=nuxi-nl.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc; bh=9+LjQk5YJnG21+NLngKYgQu8hwRS1PjSQbXIozuuwe0=; b=AYuys/6nAGus6uaJ9YN3arvxRILKViXwnEez9M3gjR9CNwoyJe2O2Ty/R+/KX46Rch 46JpdJ2nkFDYBDn44NJZq5LkPv8g6GVt2T59BJYt0Q1Q5FX3likR2TcGzbJufA3y3IzM aywso07utGNAU2XjIGC1TOL9ATYTW6ZaSeqGAJYxX0k3Wh4USMRVDr/OVwtI1bn2TQ/n fuqNP+3FnHYoHqldCduYGwXAWeh6Wvu65vQ+EDYPKWxRwaJ0RuFjxl4DO2+bEwDGStb0 WtB+HwgGafIo6iYpnhC//IDK6oQ8XxxElYLSDFY+pFFlOYD6ZiYpAeTo4ekLiKvOgqaU ekXA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc; bh=9+LjQk5YJnG21+NLngKYgQu8hwRS1PjSQbXIozuuwe0=; b=Y0qt1ImJS3MAes0FO3hcaXhwmhJY061Rq7FOiIMvMrbIm0LSyR0F+k72kcyLJRRwJI BeAJCFow/nWYxp7UqbBFA9/Bx41SkmYfsUay3ZCFBckbXL9C5MGjwW8+W7LP7F+VFWzP OtMLQynfk9I2UqB6+Psdd1VglHjSzOunKu3aF7GM9OFQUZBDRSydRK5JFfYO+niXFWui +S6trdHExWwZ6jQpDNFYQjFIxYmqQlrZsjcrkafVC9xKip+GZmrPNQyXzCE9xezgtBqV zaswQslB5jFhMH7qL4subqA3loCl0nh8JKxV1uK5nRfslimtnsKDoz5e+5TKwcOpZq7C uy1w== X-Gm-Message-State: AOPr4FVYg0DKj5l/YA/0FqElqwM/xNpL1VBaGw65C580ulgm+xHD+lAXF+zI31MF5EZNDA9AfQnBUDjZ45KdCA== MIME-Version: 1.0 X-Received: by 10.13.211.71 with SMTP id v68mr18787687ywd.310.1460990953367; Mon, 18 Apr 2016 07:49:13 -0700 (PDT) Received: by 10.129.148.6 with HTTP; Mon, 18 Apr 2016 07:49:13 -0700 (PDT) In-Reply-To: <5714DC98.7090208@selasky.org> References: <5714C86A.8050204@selasky.org> <20160418151639.634d571d@fujitsu> <5714DC98.7090208@selasky.org> Date: Mon, 18 Apr 2016 16:49:13 +0200 Message-ID: Subject: Re: qsort() documentation From: Ed Schouten To: Hans Petter Selasky Cc: Aleksander Alekseev , FreeBSD Current Content-Type: text/plain; charset=UTF-8 X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 18 Apr 2016 14:49:14 -0000 2016-04-18 15:09 GMT+02:00 Hans Petter Selasky : > On 04/18/16 14:16, Aleksander Alekseev wrote: >> I suggest also add a short description of how it was achieved >> (randomization?). > > I think the algorithm is switching to mergesort. I'll look up the paper and > add that correctly before commit. As a Dutch person, I know the answer to this. Instead of picking a fixed pivot or choosing one at random, it uses an approach called linear time median finding to find a pivot that is 'approximately median'. There are a couple of algorithms for this, but I think Bentley's qsort() uses this: https://en.wikipedia.org/wiki/Dutch_national_flag_problem -- Ed Schouten Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717