On Mon, Dec 22, 2008 at 12:29 PM, <deni...@t-online.de> wrote: > 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." >
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. -- http://mail.python.org/mailman/listinfo/python-list
