Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!know!sdd.hp.com!uakari.primate.wisc.edu!uflorida!haven!adm!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Message-ID: <5812@lanl.gov>
Date: 13 Nov 90 20:36:36 GMT
References: <16709:Nov1113:56:2390@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 12

From article <16709:Nov1113:56:2390@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> [...]
> Sorting is linear in the number of bytes being sorted. Feel free to
> spout on about implicit log n factors that don't exist; I'll continue to
> sort n-byte files in time between bn and cn seconds for nonzero b and c.
> Models of computation are cute, but I live in the real world.

So do I.  In the real world, keys are almost _never_ just one byte
long.  The log n factors implicit in radix sorts _do_ exist for any
keyspaces that are above the 'toy' level.

J. Giles