stable algorithm with complexity O(n)

[Dan Upton]

On Mon, Dec 22, 2008 at 12:29 PM,  <denisbz at t-online.de> wrote:
> On Dec 15, 10:00 pm, "cmdrrickhun... at yaho.com"
> <conrad.am... at gmail.com> wrote:
>> It can be proven that you cannot sort an arbitrarily large set of
>> numbers, given no extra information, faster than O(n log n).
>
> Cormen Leiserson and Rivest, "Algorithms", have a short clear chapter
> on
> "Sorting in linear time":
>    " ... counting sort, radix sort and bucket sort ... use operations
> other than comparisons.
>    Consequently, the Omega( n lg n ) lower bound does not apply to
> them."
>

But the key here is "given no extra information."  Your examples of
non-comparison sorts require extra information, such as knowledge
about the possible range the numbers can take on.