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: 2 Sep 93 02:38:31 GMT
From: slinky.cs.nyu.edu!slinky.cs.nyu.edu!nobody@nyu.edu  (Robert Dewar)
Subject: Re: Hoare's gripes about Ada (should be so what)
Message-ID: <263mb7$mpd@schonberg.cs.nyu.edu>
List-Id: <comp.lang.ada>

Boy this is getting off the topic, but it's hard to stand by quietly and
see blatantly incorrect technical comments.

"Sorting has been proved to take O(n log n) time"

is plain wrong. This bound applies only if the sorting is restricted to
comparisons. If arithmetic operations are required, this bound obviously
does not apply. Consider a trivial case of sorting a huge pile of numbers
in the range 1 .. 100.

This has an obvious O(N) implementation (just keep an array of 100 entries
which count the number of occurrences of each possible entry). By using
linked lists, other associated data can be carried along, still in O(N)
time.

Address distribution sorting has an expected average performance much
better than O (N long N), in fact it approaches linear performance
asymptotically in the average case if your distribution function is
well behaved. A lot of large scale sorting (the kind done on giant mainframes
with zillions of records) uses address calculation sorting.

Finally, note that in this day of parallel machines, even if you are
restricted to comparisons, you can do much better than O (N log n).