<p dir="ltr"><br /> On Jul 31, 2015 4:22 AM, "Jeremy Harris" <<a
href="mailto:jgh@wizmail.org">jgh@wizmail.org</a>>wrote:<br /> ><br /> > On 30/07/15 02:05, Peter Geoghegan
wrote:<br/> > > Since heapification is now a big fraction of the total cost of a sort<br /> > > sometimes,
evenwhere the heap invariant need not be maintained for<br /> > > any length of time afterwards, it might be
worthrevisiting the patch<br /> > > to make that an O(n) rather than a O(log n) operation [3].<br /> ><br />
> O(n log n) ?<br /> ><br /> > Heapification is O(n) already, whether
siftup(existing) or down.<br /><p dir="ltr">They are both linear on average, but the way we currently do it has an
NlogNworst case, while the other way is linear even in the worst case.<p dir="ltr">Cheers, Jeff
