Re: A worst case for qsort

From: Peter Geoghegan <pg(at)heroku(dot)com>
To: Fabien COELHO <coelho(at)cri(dot)ensmp(dot)fr>
Cc: Pg Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: A worst case for qsort
Date: 2014-08-06 06:57:07
Message-ID: CAM3SWZS3AMdRL+8B0DVrgJCFTVQWxrw0qmz00432vdTCgnAiOA@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Tue, Aug 5, 2014 at 11:49 PM, Fabien COELHO <coelho(at)cri(dot)ensmp(dot)fr> wrote:
> If so, adding some randomness in the decision process would suffice to
> counter the adversarial input argument you raised.

This is specifically addressed by the paper. Indeed, randomly choosing
a pivot is a common strategy. It won't fix the problem.

--
Peter Geoghegan

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Fujii Masao 2014-08-06 08:02:42 Re: postgresql.auto.conf and reload
Previous Message Fabien COELHO 2014-08-06 06:49:18 Re: A worst case for qsort