stable algorithm with complexity O(n)
upton at virginia.edu
Mon Dec 22 18:40:55 CET 2008
On Mon, Dec 22, 2008 at 12:29 PM, <denisbz at t-online.de> wrote:
> 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
> "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
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.
More information about the Python-list