From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
From: dewar@cs.nyu.edu (Robert Dewar)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/14
Message-ID: <dewar.839998383@schonberg>#1/1
X-Deja-AN: 174074448
references: <31FBC584.4188@ivic.qc.ca>
 <01bb83f5$923391e0$87ee6fce@timpent.airshields.com>
 	<EACHUS.96Aug12201351@spectre.mitre.org> 	<839939925snz@genesis.demon.co.uk>
 <EACHUS.96Aug13143444@spectre.mitre.org>
organization: Courant Institute of Mathematical Sciences
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-14T00:00:00+00:00
List-Id: <comp.lang.ada>


Robert Eachs says, reemphasizing an incorrect point :-)

"
  If you use the canonical heapsort it is O(2n) average, O(n log n)
worst case.  (The worst case is when each card added to the bottom of
the heap propagates to the top, using the usual version of the sort,"

No, absolutely NOT. building a heap is worst case O(N) (what the heck
does O (2N) mean -- I would take at least 25% credit off for a student
putting a junk constant like this in a big O formula!)

The proper algorithm for creating a heap is to apply what Knuth calls
siftup successively to nodes N/2, N/2-1, N/2-2 .. 1. This algorithm
is clearly linear.