Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!think.com!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Message-ID: <27347:Nov1920:16:4890@kramden.acf.nyu.edu>
Date: 19 Nov 90 20:16:48 GMT
References: <5812@lanl.gov> <4440:Nov1405:06:2590@kramden.acf.nyu.edu> <1990Nov18.025036.2498@bushido.uucp>
Organization: IR
Lines: 11

In article <1990Nov18.025036.2498@bushido.uucp> dbc@bushido.uucp (Dave Caswell) writes:
> .In the very common case that keys are not all distinct, radix sort can
> .be asymptotically FASTER than n log n, depending on the amount of
> .repetition. 
> Shouldn't this be "keys are not all the same"?

Probably. The ``not''s start to get confusing here.

Better is ``keys include duplicates.''

---Dan