Path: 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

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