Re: Randomisation for ensuring nlogn complexity in quicksort

From: Peter Geoghegan <pg(at)heroku(dot)com>
To: Atri Sharma <atri(dot)jiit(at)gmail(dot)com>
Cc: Robert Haas <robertmhaas(at)gmail(dot)com>, PgHacker <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Randomisation for ensuring nlogn complexity in quicksort
Date: 2013-07-02 15:36:38
Message-ID: CAM3SWZQchK_p8yBerKJgnz2tYvWYr1+C6=q6-fexarCKcNLuhA@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Tue, Jul 2, 2013 at 5:04 AM, Atri Sharma <atri(dot)jiit(at)gmail(dot)com> wrote:
>> I think if you'll try it you'll find that we perform quite well on
>> data sets of this kind - and if you read the code you'll see why.
>
> Right, let me read the code again from that viewpoint.

In my opinion, it would be worthwhile reading the original Bentley and
McIlroy paper [1] and using what you learned to write a patch that
adds comments throughout the canonical qsort_arg, and perhaps the
other variants.

[1] http://www.enseignement.polytechnique.fr/informatique/profs/Luc.Maranget/421/09/bentley93engineering.pdf
--
Peter Geoghegan

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2013-07-02 15:37:13 Re: Custom gucs visibility
Previous Message Fabien COELHO 2013-07-02 15:28:15 Re: New regression test time