stable algorithm with complexity O(n)

denisbz at denisbz at
Mon Dec 22 18:29:36 CET 2008

On Dec 15, 10:00 pm, "cmdrrickhun... at"
< at> 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
"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

Some of the book is in; enjoy

More information about the Python-list mailing list