Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!wuarchive!emory!att!linac!midway!msuinfo!rang
From: rang@cs.wisc.edu (Anton Rang)
Newsgroups: comp.lang.misc
Subject: Re: Sorting bounds
Message-ID: <RANG.90Nov27145400@nexus.cs.wisc.edu>
Date: 27 Nov 90 20:54:00 GMT
References: <1990Nov20.202143.10746@craycos.com>
	<6327:Nov2022:30:2490@kramden.acf.nyu.edu> <37256@nigel.ee.udel.edu>
Sender: news@msuinfo.cl.msu.edu
Organization: UW-Madison CS department
Lines: 10
In-Reply-To: carroll@cis.udel.edu's message of 26 Nov 90 19:16:45 GMT

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".
>
>  [ justification removed ]

  This assumes that all keys are distinct.

	Anton
   
+---------------------------+------------------+-------------+
| Anton Rang (grad student) | rang@cs.wisc.edu | UW--Madison |
+---------------------------+------------------+-------------+