Re: Randomisation for ensuring nlogn complexity in quicksort

From: Peter Geoghegan <pg(at)heroku(dot)com>
To: Robert Haas <robertmhaas(at)gmail(dot)com>
Cc: Atri Sharma <atri(dot)jiit(at)gmail(dot)com>, PgHacker <pgsql-hackers(at)postgresql(dot)org>
Subject: Re: Randomisation for ensuring nlogn complexity in quicksort
Date: 2013-07-01 21:21:18
Message-ID: CAM3SWZRHi=T2-xPLg4aANHTPqoqkKR3jUctomxHD3D0k-5Zt9w@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

On Mon, Jul 1, 2013 at 12:32 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> I have been reading the recent discussion and was researching a bit, and I think that we should really go with the idea of 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.

+1

--
Peter Geoghegan

In response to

Browse pgsql-hackers by date

  From Date Subject
Next Message Alvaro Herrera 2013-07-01 21:25:45 Re: pg_resetxlog -m documentation not up to date
Previous Message Greg Smith 2013-07-01 21:07:36 Re: fallocate / posix_fallocate for new WAL file creation (etc...)