On Dec 15, 10:00 pm, "[email protected]"
<[email protected]> 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
--
http://mail.python.org/mailman/listinfo/python-list
