Re: Too Many Packages [was Re: Splitting locales...]
On Tue, Oct 10, 2000 at 03:48:23PM +0200, Daniele Cruciani wrote:
> Hi, I've follow this thread without a great concentration, but now ...
>
> That radix sort sound to me as an absurd: I've read a prove of that
> lower bound of sorting in a sequencial architetture is O(n log n)
> [Prof. Paolo Zellini, CNR] . I don't remember literally the prove, but
> it was correct (my professor Milvio Capovani, second it, and me too of
> course :).
>
> 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 famous proof applies only to comparison sorts. Comparison sorts
are general, they work on any data which is totally ordered.
However, other sorts which don't use compare() routines, but instead
exploit some property or shape of the data can go much
faster. (Stupid, but important, example: How fast can you sort the
numbers 1...n? Answer: O(n), the cost of printing out the answer,
which you know in advance!).
Ref: Knuth volume 3, I think.
> 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).
I'm not aware of anjy parallel algorithm which is particularly clever.
Jules
Reply to: