Article View: comp.lang.misc
Article #2181Re: A very brief history of optimal sorting methods
From: Dan Bernstein
Date: Mon, 19 Nov 1990 20:16
Date: Mon, 19 Nov 1990 20:16
11 lines
923 bytes
923 bytes
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
Technical Details
Message-ID:
<27347:Nov1920:16:4890@kramden.acf.nyu.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!think.com!yale!cmcl2!kramden.acf.nyu.edu!brnstndReferences:
<5812@lanl.gov> <4440:Nov1405:06:2590@kramden.acf.nyu.edu> <1990Nov18.025036.2498@bushido.uucp>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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