Re: Too Many Packages [was Re: Splitting locales...]

[tb@becket.net (Thomas Bushnell, BSG)]

Daniele Cruciani <cruciani@cli.di.unipi.it> writes:

>  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 :).

That proof is for sorts when you have only a single comparison
function.  Radix sort takes advantage of additional structure in the
data space.