Greg Stark <stark@mit.edu> writes:
> http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
Interesting. I'm pretty sure that idea appears nowhere in Knuth
(which might mean it's new enough to have a live patent on it ...
anybody know who invented this?). But it seems like that should buy
back enough comparisons to justify leaving the next-run tuples out of
the heap (unordered) until the heap becomes empty. You still want to
insert new tuples into the heap if they can go to the current run, of
course.
regards, tom lane