Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!caen!uflorida!haven!adm!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Sorting bounds
Message-ID: <4343:Nov2720:36:5790@kramden.acf.nyu.edu>
Date: 27 Nov 90 20:36:57 GMT
References: <1990Nov21.211000.11359@craycos.com> <29686:Nov2505:33:4290@kramden.acf.nyu.edu> <1B779_7@xds13.ferranti.com>
Organization: IR
Lines: 21

In article <1B779_7@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes:
> In article <29686:Nov2505:33:4290@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
> > I'm sorry I didn't dismiss this strongly enough in my first response. It
> > is absolutely irrelevant how long it takes to pick one of N buckets. All
> > radix sort uses is picking one of a constant number (you said K at
> > first) of buckets. For definiteness, let's settle upon K as being 256
> > for all time. It takes constant time, in theory and in practice, to
> > select one of 256 buckets.
> How about picking 2 buckets? Does it still work? In constant time?

Yes. In constant time. Why anyone would want to use eight passes with
lots of bit manipulation where one much simpler pass would suffice, I
don't know.

> Would it not be safe to assume that it takes O(log(key length)) time to do
> something with the bucket once you've found it, assuming that the key length
> is greater than log2(buckets)?

Why would you assume something like that?

---Dan