Re: Randomisation for ensuring nlogn complexity in quicksort

On Sun, Jun 30, 2013 at 8:30 AM, Atri Sharma <atri.jiit@gmail.com> wrote:
> I have been reading the recent discussion and was researching a bit, and I think that we should really go with the
ideaof randomising the input data(if it is not completely presorted), to ensure that we do not get quadratic
complexity.

That doesn't ensure any such thing.  It just makes it less likely.
But we have existing guards that also make that unlikely, so I'm not
sure what we'd be gaining.

> One easy way to do that could be to take a sample of the data set, and take a pivot out of it. Still a better way
couldbe to take multiple samples which are spread of the data set, select a value from each of them, and then take a
cumulativepivot(median,maybe). 

We pretty much do that already.

> This shouldn't be too complex, and should give us a fixed nlogn complexity even for wild data sets, without affecting
existingnormal data sets that are present in every day transactions. I even believe that those data sets will also
benefitfrom the above optimisation. 

The only method of selecting a pivot for quicksort that obtain O(n lg
n) run time with 100% certainty is have a magical oracle inside the
computer that tells you in fixed time and with perfect accuracy which
pivot you should select.

If you want to get a useful response to your emails, consider
including a statement of what you think the problem is and why you
think your proposed changes will help.  Consider offering a test case
that performs badly and an analysis of the reason why.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company