From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.5-pre1 (2020-06-20) on
	ip-172-31-74-118.ec2.internal
X-Spam-Level: 
X-Spam-Status: No, score=-0.0 required=3.0 tests=BAYES_20 autolearn=ham
	autolearn_force=no version=3.4.5-pre1
Date: Thu, 2 Sep 93 5:39:32 MDT
From: Colin James 0621 <cjames@dsc.blm.gov>
Subject: RE: Hoare's gripes about Ada (should be who so what)
Message-ID: <9309020539.aa05156@dsc.blm.gov>
List-Id: <comp.lang.ada>

  
Peter Juhl at AT&T writes that it is unclear to which big-O statistics
I refer.  See Donald Knuth, "The Art of Computer Programming", Volume 3
Sorting / Searching, 1973, p 381.  Juhl terms distribution counting as
radix sorting.  This is theoretically true, but practically mistaken.
See Robert Sedgwick's "Algorithms", 1983, p 99 ff.  Knuth warns that
distribution counting "is very useful when keys have a small range"
(p 379) and that "[r]adix sorting should not be used for small N!"
(p 380).
  
For those interested in the source code, I have been deluged by requests
but haven't been able to post the C source yet on the Xenix box at work.
urce code (and working implementations in TrueBASIC
which are portable and easy to translate) can be found on CEC Services 
BBS at (303) 231 - 9438, use account "tdsdemo" and password "demo".  At
the prompt type "fb" to see the files available.  To view and capture the
C pseudo code type "v dcntsort.txt".  The pseudo code is after Sedgwick's
Pascal pseudo code.