Sort one sequence by O(n) in time and O(1) in space

[Steven D'Aprano]

On Mon, 10 Feb 2014 10:20:33 +0000, Sturla Molden wrote:

> Wesley <nispray at gmail.com> wrote:
>> [Wesley] This is not homework:-)
>> And actually I am new to algorithm, so you guys can feel free to say
>> anything you want
> 
> In general, we cannot sort a sequence in O(n) time. O(n log n) is the
> lower bound on the complexity.

Firstly, you're talking about average complexity, not best-case 
complexity. The base-case can be O(N) for a sequence which is already 
sorted. Worst case can be much greater, e.g. O(N**2) for Quicksort, or 
unbounded for Bogosort. (That is, Bogosort is not guaranteed to sort a 
sequence even after infinite time!)

Secondly, O(N*log N) applies to *comparison sorts*. Non-comparison sorts 
such as radix-, counting- and bucket-sort have average case complexity of 
O(N). See, for example:

http://algorithmstwo.soc.srcf.net/resources/asides/noncomparison/

http://en.wikipedia.org/wiki/Bead_sort

http://en.wikipedia.org/wiki/Radix_sort

http://en.wikipedia.org/wiki/Spaghetti_sort


etc.


-- 
Steven