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: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,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/18
Message-ID: <dewar.840351477@schonberg>#1/1
X-Deja-AN: 174872485
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>
 <4umeot$re2@hil-news-svc-2.compuserve.com> <dewar.839831192@schonberg>
 <4v2fb9$lpj@news.utdallas.edu> <dewar.840250400@schonberg>
 <4v63jv$iqp@news.utdallas.edu>
organization: Courant Institute of Mathematical Sciences
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-18T00:00:00+00:00
List-Id: <comp.lang.ada>


Steve said

">No, they are much simpler to analyze, analyzing the left to right
>radix sort (the only reasonable implementation, the right to left sort
>is never a good choice), or the address calculation sort, is not easy.
  Never? That's interesting, because it has very predictable behavior
and runs very quickly (given enough real memory)."

Well if the key is one digit, then of course you just have a counting
sort and it is fine, but if the key is any significant number of
digits, then NlogN < KN, e.g. 32 bit numbers with less than 2**32
of them to sort!