Mathsort (was: builtin functions)

[Gregory Smith]

In article <2554 at utcsri.UUCP> greg at utcsri.UUCP (Gregory Smith)[me] writes:
>Now for something completely different...
>From: g-rh at cca.UUCP (Richard Harter)
>>	Grumble, grumble.  Sorry, this is a real practical problem.
>>	Let me give some context.  Suppose you are doing a high speed
>>	sort of character strings.  Being a clever fellow you have
>>	read the glossed over parts of the literature and have seen
>>	that a math sort is O(n) rather than O(n log n).  You also
>>	notice that it is cheaper to compare 4 bytes at once with
>>	an 32-bit integer compare than to make 4 byte compares.
>
>I'm not sure on this - isn't it ridiculous to do a mathsort of 32-bit
>ints? In O(n) above ( for the mathsort) doesn't n become 2^32 rather
>than the list size? If so, it would of course be even sillier for
>larger ( i.e. reasonably-sized ) char strings.

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?
-- 
"If you aren't making any mistakes, you aren't doing anything".
----------------------------------------------------------------------
Greg Smith     University of Toronto      UUCP: ..utzoo!utcsri!greg