Article View: comp.lang.misc
Article #2051Re: A very brief history of optimal sorting methods
From: Dan Bernstein
Date: Wed, 14 Nov 1990 05:06
Date: Wed, 14 Nov 1990 05:06
18 lines
1249 bytes
1249 bytes
In article <5812@lanl.gov> jlg@lanl.gov (Jim Giles) writes: > From article <16709:Nov1113:56:2390@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein): > > 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. Sorting is linear in the number of bytes being sorted. The length of the keys is absolutely, entirely irrelevant to this conclusion. > The log n factors implicit in radix sorts _do_ exist for any > keyspaces that are above the 'toy' level. 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. The ``implicit'' factor that all you computer scientists keep imagining does NOT exist. ---Dan
Technical Details
Message-ID:
<4440:Nov1405:06:2590@kramden.acf.nyu.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstndReferences:
<16709:Nov1113:56:2390@kramden.acf.nyu.edu> <5812@lanl.gov>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!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: <4440:Nov1405:06:2590@kramden.acf.nyu.edu> Date: 14 Nov 90 05:06:25 GMT References: <16709:Nov1113:56:2390@kramden.acf.nyu.edu> <5812@lanl.gov> Organization: IR Lines: 18