*To*: debian-devel@lists.debian.org*Subject*: Re: Too Many Packages [was Re: Splitting locales...]*From*: William Lee Irwin III <wli@holomorphy.com>*Date*: Tue, 10 Oct 2000 11:45:26 -0700*Message-id*: <20001010114526.A13135@holomorphy.com>*Mail-followup-to*: William Lee Irwin III <wli@holomorphy.com>, debian-devel@lists.debian.org*In-reply-to*: <20001010155858.F17938@blueberry.jellybean.co.uk>; from jules@jellybean.co.uk on Tue, Oct 10, 2000 at 03:58:58PM +0100*References*: <20001009220553.0BBD715713@zaphod> <874s2l2ysp.fsf@becket.becket.net> <877l7h1j77.fsf@becket.becket.net> <20001010154823.A1088@colossus.cli.di.unipi.it> <20001010155858.F17938@blueberry.jellybean.co.uk>

On Tue, Oct 10, 2000 at 03:48:23PM +0200, Daniele Cruciani wrote: >> So, now I've a problem: cause I've surely missunderstood what the >> matter here and what is for radix sort, I've loose where's documented >> that alghoritms and how it can "sort" something in linear time (if it >> do sort at all). The general idea behind radix sort and bucket sort is address calculation. Radix sort specifically relies on trie-like mappings from the list/array elements to "buckets" where things with common digits are stored. The ingenious part is sorting from least to most significant digits. Bucket sort uses quantiles instead of digits. The important part of these sorting techniques is that the "buckets" in both radix sort and bucket sort are ordered. On Tue, Oct 10, 2000 at 03:58:58PM +0100, Jules Bean wrote: > The famous proof applies only to comparison sorts. Comparison sorts > are general, they work on any data which is totally ordered. The famous proof simply says that a comparison/exchange sort is equivalent to a binary decision tree, and as there are n! permutations of n letters, the decision tree must have n! nodes, and hence height lg n! and this is the lower time bound n lg n (note this is slightly pessimistic; lg n! = o(n lg n)). On Tue, Oct 10, 2000 at 03:48:23PM +0200, Daniele Cruciani wrote: >> I'm interested in parallel alghorithms so, if radix sort is such an >> alghoritms, I'll be happy to read about it. If it isn't and does some >> strange work over string, require more space and such I'll be happy to >> known it the same (curiosity). On Tue, Oct 10, 2000 at 03:58:58PM +0100, Jules Bean wrote: > I'm not aware of anjy parallel algorithm which is particularly clever. There is a fairly obvious parallel implementation of both radix and bucket sort. Bucket sort: sort the quantile buckets in parallel Radix sort: stuff buckets by the most significant digit for one pass sort those buckets in parallel Knuth notes that there were some MSD-first radix sorters out there during the dark ages; actually, the parallel radix sort as it's being described here is actually a bucket sort (beware of clashing terminology) with radix sort as the routine being used on the quantiles, and is covered by the first strategy. Cheers, Bill -- "The good Christian should beware of mathematicians and all those who make empty prophecies. The danger already exists that mathematicians have made a covenant with the devil to darken the spirit and confine man in the bonds of Hell." -- St. Augustine

**Follow-Ups**:**Re: Too Many Packages [was Re: Splitting locales...]***From:*Daniele Cruciani <cruciani@cli.di.unipi.it>

**References**:**Re: Too Many Packages [was Re: Splitting locales...]***From:*Buddha Buck <bmbuck@14850.com>

**Re: Too Many Packages [was Re: Splitting locales...]***From:*tb@becket.net (Thomas Bushnell, BSG)

**Re: Too Many Packages [was Re: Splitting locales...]***From:*tb@becket.net (Thomas Bushnell, BSG)

**Re: Too Many Packages [was Re: Splitting locales...]***From:*Daniele Cruciani <cruciani@cli.di.unipi.it>

**Re: Too Many Packages [was Re: Splitting locales...]***From:*Jules Bean <jules@jellybean.co.uk>

- Prev by Date:
**Re: What to do with transient bugs?** - Next by Date:
**Re: kernel 2.4.0-test9 and Cisco Pix Firewall - Might be a bug???** - Previous by thread:
**Re: Too Many Packages [was Re: Splitting locales...]** - Next by thread:
**Re: Too Many Packages [was Re: Splitting locales...]** - Index(es):