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

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

tb@becket.net (Thomas Bushnell, BSG) writes:

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

To be more precise, suppose we are sorting N digit strings with max
M.  (Each digit string represents a number, and the largest number is
M; the strings are thus log(M) digits long.)

Real computers have constant time comparison operations only for
strings of finite length.  Comparing strings of unbounded length will
take log(M) time.  Now mergesort takes O(n log n) comparisons, but
each one is (log M) in length.  So this means that mergesort is now
O(N log(N) log(M)) in time.

Radix sort requires O(N log(M)) total time, by the argument you gave.

If you want to pretend that comparisons are constant time, you can do
that by factoring out the log(M) time, but only by saying the strings
are of limited length, in which case you also factor out the same
log(M) time from the radix sort.