Article View: comp.lang.misc
Article #2254Re: Sorting bounds
From: Peter da Silva
Date: Wed, 28 Nov 1990 15:43
Date: Wed, 28 Nov 1990 15:43
15 lines
1230 bytes
1230 bytes
In article <RANG.90Nov27145400@nexus.cs.wisc.edu> rang@cs.wisc.edu (Anton Rang) writes: > In article <37256@nigel.ee.udel.edu> carroll@cis.udel.edu (Mark Carroll) writes: > >Saying that sorting is "linear in the number of bytes" is truly foolish. > >It's nothing but a deceptive way of saying "Sorting takes time O(n lg n) > >in the number of keys". > This assumes that all keys are distinct. If they're not you can take an initial O(n) pass sticking all the equal keys together. Now your problem becomes sorting (n') new keys, which is again O(n' log n'). -- Peter da Silva. `-_-' +1 713 274 5180. 'U` peter@ferranti.com
Technical Details
Message-ID:
<SOV7LG9@xds13.ferranti.com>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!watserv1!watmath!att!att!linac!pacific.mps.ohio-state.edu!zaphod.mps.ohio-state.edu!lavaca.uh.edu!menudo.uh.edu!sugar!ficc!peterReferences:
<1990Nov20.202143.10746@craycos.com> <6327:Nov2022:30:2490@kramden.acf.nyu.edu> <37256@nigel.ee.udel.edu> <RANG.90Nov27145400@nexus.cs.wisc.edu>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!utgpu!watserv1!watmath!att!att!linac!pacific.mps.ohio-state.edu!zaphod.mps.ohio-state.edu!lavaca.uh.edu!menudo.uh.edu!sugar!ficc!peter From: peter@ficc.ferranti.com (Peter da Silva) Newsgroups: comp.lang.misc Subject: Re: Sorting bounds Message-ID: <SOV7LG9@xds13.ferranti.com> Date: 28 Nov 90 15:43:07 GMT References: <1990Nov20.202143.10746@craycos.com> <6327:Nov2022:30:2490@kramden.acf.nyu.edu> <37256@nigel.ee.udel.edu> <RANG.90Nov27145400@nexus.cs.wisc.edu> Reply-To: peter@ficc.ferranti.com (Peter da Silva) Organization: Xenix Support, FICC Lines: 11