Article View: comp.lang.misc
Article #2256Re: Sorting bounds
From: Dan Bernstein
Date: Thu, 29 Nov 1990 12:53
Date: Thu, 29 Nov 1990 12:53
17 lines
1142 bytes
1142 bytes
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
Technical Details
Message-ID:
<6239:Nov2912:53:1990@kramden.acf.nyu.edu>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!rutgers!uwm.edu!rpi!sci.ccny.cuny.edu!phri!cmcl2!kramden.acf.nyu.edu!brnstndReferences:
<1B779_7@xds13.ferranti.com> <4343:Nov2720:36:5790@kramden.acf.nyu.edu> <OOV7NC9@xds13.ferranti.com>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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