Re: Pentatonic mode and a solution to the order of the primes...
> BTW, is it really linear? I've always thought sorting was O(n log n),Sorting is provably O(n log n) and no better _if_ it is only based on
> although some people described supposedly O(n) sorts but there
> always seemed to be some sort of catch.
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
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