Re: A worst case for qsort - Mailing list pgsql-hackers

From Fabien COELHO
Subject Re: A worst case for qsort
Date
Msg-id alpine.DEB.2.10.1408061548010.28413@sto
Whole thread Raw
In response to Re: A worst case for qsort  (Peter Geoghegan <pg@heroku.com>)
Responses Re: A worst case for qsort
List pgsql-hackers
>> 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.

Too bad. I must admit that I do not see how to build a test case which 
would trigger a worst case behavior against a qsort which chooses the 
pivot randomly, but I have not read the paper, and possibly there is an 
element of context which is eluding me.

-- 
Fabien.



pgsql-hackers by date:

Previous
From: Marko Tiikkaja
Date:
Subject: pgcrypto: PGP signatures
Next
From: Fabien COELHO
Date:
Subject: Re: Enhancing pgbench parameter checking