## Re: Pentatonic mode and a solution to the order of the primes...

Expand Messages
• ... Sorting is provably O(n log n) and no better _if_ it is only based on comparing 2 elements at a time, e.g. with
Message 1 of 5 , Feb 11, 2005
> BTW, is it really linear? I've always thought sorting was O(n log n),
> although some people described supposedly O(n) sorts but there
> always seemed to be some sort of catch.

Sorting is provably O(n log n) and no better _if_ it is only based on
comparing 2 elements at a time, e.g. with <.

If something useful is known about the elements, e.g. so they can easily be
divided into certain subsets, then sorting often becomes O(n).

Sorting integers is linear if the bits (or digits) can be extracted in linear
time.
With bits, the numbers can be placed in a binary tree with 0=left and 1=right
in linear time. The sorted numbers can then be read in linear time by
traversing the tree.

Alphabetic sorting is linear if the letters can be extracted. E.g. place words
in a tree with 26 children for each node.

Sorting floats is linear e.g. if the binary representation can be recovered
and understood. Then the mantissa and exponent can be sorted separately.

In practice on typical sizes, linear sorting algorithms may often turn out
slower or require more space than practical.

--
Jens Kruse Andersen
Your message has been successfully submitted and would be delivered to recipients shortly.