> 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