Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!uwm.edu!rpi!sci.ccny.cuny.edu!phri!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Sorting bounds
Message-ID: <6239:Nov2912:53:1990@kramden.acf.nyu.edu>
Date: 29 Nov 90 12:53:19 GMT
References: <1B779_7@xds13.ferranti.com> <4343:Nov2720:36:5790@kramden.acf.nyu.edu> <OOV7NC9@xds13.ferranti.com>
Organization: IR
Lines: 17

In article <OOV7NC9@xds13.ferranti.com> peter@ficc.ferranti.com (Peter da Silva) writes:
> > > 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.
> OK, you then need to use 8 passes. With a larger sample size you need
> to use more passes.

Wrong. Who said anything about sample size?

> The number of passes increase as the log of the
> sample size.

No, the number of passes does not increase as the log of the sample
size. Do you understand how an MSD radix sort works?

---Dan