Re: Re: Using quicksort and a merge step to significantly improve on tuplesort's single run "external sort"

On Sat, Aug 1, 2015 at 9:49 AM, Jeremy Harris <jgh(at)wizmail(dot)org> wrote:
> On 31/07/15 18:31, Robert Haas wrote:
>> On Fri, Jul 31, 2015 at 7:21 AM, Jeremy Harris <jgh(at)wizmail(dot)org> wrote:
>>> Heapification is O(n) already, whether siftup (existing) or down.
>>
>> That's not my impression, or what Wikipedia says. Source?
>
> Measurements done last year:
>
> http://www.postgresql.org/message-id/52F35462.3030306@wizmail.org
> (spreadsheet attachment)
>
> http://www.postgresql.org/message-id/52F40CE9.1070509@wizmail.org
> (measurement procedure and spreadsheet explanation)

I don't think that running benchmarks is the right way to establish
the asymptotic runtime of an algorithm. I mean, if you test
quicksort, it will run in much less than O(n^2) time on almost any
input. But that does not mean that the worst-case run time is
anything other than O(n^2).

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