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:56 AM, Andres Freund <andres(at)anarazel(dot)de> wrote:
> On 2015-07-31 13:31:54 -0400, 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?
>
> 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

That doesn't really address the sift-up vs. sift-down question. Maybe
I'm just confused about the terminology. I think that Wikipedia
article is saying that if you iterate from the middle element of an
unsorted array towards the beginning, establishing the heap invariant
for every item as you reach it, you will take only O(n) time. But
that is not what inittapes() does. It instead starts at the beginning
of the array and inserts each element one after the other. If this is
any different from building the heap via successive insertions, I
don't understand how.

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