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

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

Buddha Buck <bmbuck@14850.com> writes:

> Because a proper analysis of radix sort will say that sorting n strings 
> is O(n*m), where m is the length of the strings (you have to do m 
> passes of distribution and collection of the n items to sort, so you 
> pass through all the data 2*m times).  But if you a) have a total of b 
> buckets, and b) have n distinct strings, then the string length m > log 
> n (base b).  So for arbitrary length strings, you have O(n log n).

But if you calculate that way, then mergesort now takes O(n log^2 n).
In other words, there is a hidden factor for mergesort, because
comparing items isn't a constant operation, but is log n in the size
of the items.