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

On 2015-07-31 13:31:54 -0400, Robert Haas wrote:
> On Fri, Jul 31, 2015 at 7:21 AM, Jeremy Harris <jgh@wizmail.org> wrote:
> > Heapification is O(n) already, whether siftup (existing) or down.
> 
> That's not my impression, or what Wikipedia says.  Source?

Building a binary heap via successive insertions is O(n log n), but
building it directly is O(n). Looks like wikipedia agrees too
https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
I'm pretty sure that there's a bunch of places where we intentionally
build a heap at once instead successively. At least reorderbuffer.c does
so, and it looks like nodeMergeAppend as well (that's why they use
binaryheap_add_unordered and then binaryheap_build).

Greetings,

Andres Freund