Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site cca.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!bellcore!decvax!cca!g-rh
From: g-rh@cca.UUCP (Richard Harter)
Newsgroups: net.lang.c
Subject: Re: Mathsort (was: builtin functions)
Message-ID: <7386@cca.UUCP>
Date: Sat, 19-Apr-86 23:27:11 EST
Article-I.D.: cca.7386
Posted: Sat Apr 19 23:27:11 1986
Date-Received: Mon, 21-Apr-86 07:43:03 EST
References: <2524@brl-smoke.ARPA> <2554@utcsri.UUCP> <>
Reply-To: g-rh@cca.UUCP (Richard Harter)
Organization: Computer Corp. of America, Cambridge
Lines: 35
Summary: 

In article <> greg@utcsri.UUCP (Gregory Smith) writes:
>
>Sorry for posting stuff in my sleep - I'm straight on this now. A mathsort
>is really O(n+m) where n is the list size and m is the difference between the
>largest and the smallest numbers in the list. (If you don't know the min and
>max, then m is the largest possible range ). Mathsort is only useful when
>m is considerably less than n - e.g. a list of 10K numbers, all in the range
>1 to 100. ( n=10K,m=100). So when a mathsort is useful, it is O(n). Of
>course, you also need a table of size m. In the above example, though, m
>is on the order of 2^32 and thus the time would be O(m), since m would
>dominate, and and the table would be ridiculously huge. Do you really
>think the mathsort would be 'glossed over' as much as it is if it was capable
>of sorting arbitrary 32-bit numbers in O(n) time?
>-- 

	I've already gone over this in another article.  However to deal
with the O(n+m) question:  you map the actual range, m, into a smaller
range by a transformation.  The number of operations is, indeed, O(n),
subject to restrictions on the distribution of keys.

	The subject of math sorts is glossed over.  I suspect that there
there are two reasons for this.  The first is that the theory of
comparison sorts is (a) elegant and (b) independent of the distribution
of key values.  This is a real factor -- many authors focus on material
where the underlying theory is interesting from a theoretical point of
view.  The second reason is that implementation of a good math sort is
tricky -- it is very easy to have performance blow up for a variety of
subtle reasons.

	On a more general note, it is naive to suppose that the most
commonly used techniques and algorithms are the best available.  There
are so many possible algorithms and so much that has been done that
everybody is drowned in information.

		Richard Harter, SMDS Inc.