stable algorithm with complexity O(n)

[denisbz at t-online.de]

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

Some of the book is in books.google.com; enjoy