Article View: comp.lang.misc
Article #2190Re: A very brief history of optimal sorting methods
From: Dan Bernstein
Date: Tue, 20 Nov 1990 04:46
Date: Tue, 20 Nov 1990 04:46
17 lines
1136 bytes
1136 bytes
In article <157@garth.UUCP> smryan@garth.UUCP (Steven Ryan) writes: > >Sorting is linear in the number of bytes being sorted. This is true both > >theoretically and practically. > What is the theoretical and practical relation between the number of bytes > and the number keys (records). If you have b bytes and n keys, which is true: > b = kn > b = k n log n > b > k n log n ? None of the above is always true. That's why it's so much more natural to report sorting times per byte---measures per key are necessarily imprecise. If the keys are of fixed length, b is kn. If the keys are all distinct, b is at least n log_2 n. ---Dan
Technical Details
Message-ID:
<9921:Nov2004:46:0990@kramden.acf.nyu.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!haven!adm!cmcl2!kramden.acf.nyu.edu!brnstndReferences:
<4248@goanna.cs.rmit.oz.au> <24945:Nov1218:54:5590@kramden.acf.nyu.edu> <157@garth.UUCP>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!haven!adm!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: <9921:Nov2004:46:0990@kramden.acf.nyu.edu> Date: 20 Nov 90 04:46:09 GMT References: <4248@goanna.cs.rmit.oz.au> <24945:Nov1218:54:5590@kramden.acf.nyu.edu> <157@garth.UUCP> Organization: IR Lines: 17