Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!helios!bcm!dimacs.rutgers.edu!seismo!ukma!uflorida!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!wuarchive!udel!ee.udel.edu
From: new@ee.udel.edu (Darren New)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Message-ID: <36568@nigel.ee.udel.edu>
Date: 16 Nov 90 16:36:13 GMT
References: <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <235@smds.UUCP> <16709:Nov1113:56:2390@kramden.acf.nyu.edu>
Sender: usenet@ee.udel.edu
Organization: University of Delaware
Lines: 34
Nntp-Posting-Host: estelle.ee.udel.edu

In article <16709:Nov1113:56:2390@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>Sorting is linear in the number of bytes being sorted. Feel free to
>spout on about implicit log n factors that don't exist; I'll continue to
>sort n-byte files in time between bn and cn seconds for nonzero b and c.
>Models of computation are cute, but I live in the real world.

Actually, for sorting to be linear in the number of bytes sorted, don't
you need some opperation on the keys other than comparison?  For
example, how would you sort (say, in Pascal) an array of floats (reals,
whatever) without using division or multiplication and still have it
take linear time?

How about this:

"I want you to sort this array of encrypted passwords into the same
order as the user numbers they belong to. Since for security reasons I
cannot reveal to your program the user number belonging to each
password, I will provide a function "porder(A,B)" which returns true if
the user number for password A comes before the user number for
password B and false otherwise. Since the user number space is very
sparse, this will not compromise security."

In this case, you will need O(n log n) calls to the porder function,
hence taking O(n log n) time, regardless of how big the keys are. This
is easy to see based on a decision-tree argument. In this case, you
really don't even have the keys (the user number), but only pointers to
keys (the passwords). I would be *very* interested to see some
(pseudo-) code that does such a sort in linear time.
                      -- Darren
-- 
--- Darren New --- Grad Student --- CIS --- Univ. of Delaware ---
----- Network Protocols, Graphics, Programming Languages, 
      Formal Description Techniques (esp. Estelle), Coffee, Amigas -----
              =+=+=+ Let GROPE be an N-tuple where ... +=+=+=