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: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
From: eachus@spectre.mitre.org (Robert I. Eachus)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/14
Message-ID: <EACHUS.96Aug14184451@spectre.mitre.org>#1/1
X-Deja-AN: 174238963
references: <31FBC584.4188@ivic.qc.ca>
 <01bb83f5$923391e0$87ee6fce@timpent.airshields.com>
organization: The Mitre Corp., Bedford, MA.
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>


In article <dewar.839998195@schonberg> dewar@cs.nyu.edu (Robert Dewar) writes:

  > Building a heap is a worst case O(N) process. I have seen it
  > occasionally misdescribed in a form that would be N logN, but if
  > you look at the original treesort3, you will see that the heap
  > building phase is clearly linear (the proof is straightforward, I
  > can share it offline if you like).

   Ah, the joys of being an old fart:

   Williams, J. W. J.  Algorithm 232: Heapsort, Comm. ACM 7:6, 347-348
   Floyd, R. W. Algorithm 245: treesort3, Comm. ACM 7: 12, 701

   There was a time when NO ONE knew how to build a heap in O(n) time,
but it didn't last long.  However, I was very interesting in sorting
problems right then.  Robert Dewer must have come along a little
later, when treesort3 had almost completely replaced Heapsort.  But
they are two different (but closely related) algorithms.  This is why
I have been complaining about the mixup in names.

   And for those of you who weren't around then, the reason for using
these sorts, and not quicksort was that you were really doing a
polyphase mergesort from tapes, and the inmemory sort of lots of
"little" files that could fit in memory was a first step.  Among other
things, the elimination of the need for stack space--for quicksort--
meant you could sort a slightly larger file. And that stack was
usually hand coded if you did use Quicksort...

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...