On Dec 15, 10:00 pm, "cmdrrickhun...@yaho.com" <conrad.am...@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 -- http://mail.python.org/mailman/listinfo/python-list