Path: 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: 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> Reply-To: peter@ficc.ferranti.com (Peter da Silva) Organization: Xenix Support, FICC Lines: 11 In article 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