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: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,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/24
Message-ID: <dewar.840897485@schonberg>#1/1
X-Deja-AN: 176205389
references: <31FBC584.4188@ivic.qc.ca>
 	 <01bb83f5$923391e0$87ee6fce@timpent.airshields.com>
 	 <4uah1k$b2o@solutions.solon.com>
 	 <01bb853b$ca4c8e00$87ee6fce@timpent.airshields.com>
 	 <4udb2o$7io@solutions.solon.com> <EACHUS.96Aug8155946@spectre.mitre.org>
 	 <dewar.839593893@schonberg> <4uvi6j$1brg@watnews1.watson.ibm.com>
 <321886DA.15FB7483@escmail.orl.mmc.com> <4vjtaa$6bq@goanna.cs.rmit.edu.au>
organization: Courant Institute of Mathematical Sciences
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-24T00:00:00+00:00
List-Id: <comp.lang.ada>


Richard said

"There is another factor:  heap sort requires moving one's attention from
card [i] to card [i/2]; this is a very expensive operation for people.
The only way I would be able to do it with any reasonable speed is to
write the indices on the table and scan for a match instead of counting.
In contrast, insertion sort requires _no_ human counting, just move left
one and detect end of sequence, and depending on the size of the cards,
can benefit from a "block move".  (With a standard card deck, I could
probably move >5 cards up a position at once.)
"

Oh gosh no!!!

Arrange the cards in a heap layed out as a binary tree, nothing else
makes sense if you are using heap sort on cards. Remember that the
[i] to [i/2] business is just a trick for mapping the underlying binary
tree!